QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #382712 | #3742. 卖萌表情 | ucup-team1251 | WA | 27ms | 49108kb | C++17 | 3.5kb | 2024-04-08 17:59:56 | 2024-04-08 17:59:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
typedef vector<int> vec;
typedef vector<vec> mat;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int dp1[2000][2000], dp2[2010][2010];
char a[5200][5020],b[2020][2020];
void solve()
{
int n, m;
while(cin >> n >> m){
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp1[0][i] = 0;
dp2[0][i] = 0;
dp1[i][0] = 0;
dp2[i][0] = 0;
dp1[i][j] = 0;
dp2[i][j] = 0;
cin >> a[i][j];
b[j][i] = a[i][j];
}
}
// for (int i = 1; i <= m;i++){
// for (int j = 1; j <= n;j++){
// cout << b[i][j];
// }
// cout << '\n';
// }
dp1[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j] == 'v' && i - 1 >= 1)
{
if (j+1<=m&&a[i - 1][j - 1] == '^' && a[i - 1][j + 1] == '^')
{
if (j - 2 >= 1 && a[i][j - 2] == 'v')
dp1[i][j] = max(dp1[i][j], dp1[i][j - 3] + 1);
else
{
dp1[i][j] = max(dp1[i][j], dp1[i][j - 1] + 1);
}
}
if (j - 2 >= 1 && a[i][j - 2] == 'v' && a[i - 1][j - 1] == '^')
{
dp1[i][j] = max(dp1[i][j], dp1[i][j - 3] + 1);
dp1[i][j - 2] = max(dp1[i][j - 2], dp1[i][j]);
}
}
dp1[i][j] = max(dp1[i][j], dp1[i][j - 1]);
}
dp1[i+1][0] = dp1[i][m];
}
dp2[0][0] = 0;
for (int i = 1; i <= m;i++){
for (int j = 1; j <= n;j++){
if (b[i][j] == '>' && i - 1 >= 1)
{
if (j+1<=n&&b[i - 1][j - 1] == '<' && b[i - 1][j + 1] == '<')
{
if (j - 2 >= 1 && b[i][j - 2] == '>')
dp2[i][j] = max(dp2[i][j], dp2[i][j - 3] + 1);
else
{
dp2[i][j] = max(dp2[i][j], dp2[i][j - 1] + 1);
}
}
if (j - 2 >= 1 && b[i][j - 2] == '>' && b[i - 1][j - 1] == '<')
{
dp2[i][j] = max(dp2[i][j], dp2[i][j - 3] + 1);
dp2[i][j - 2] = max(dp2[i][j - 2], dp2[i][j]);
}
}
dp2[i][j] = max(dp2[i][j], dp2[i][j - 1]);
}
dp2[i+1][0] = dp2[i][n];
}
cout << dp1[n][m] + dp2[m][n]<< '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
// 1 2 3 4 5 6 7 8 9 10
// 2 5 9 14 20 27 35 44 54 65
// 3 9 23 43 70 105 149 203 268 345
// 4 14 43 113 218 367 570 838 1183 1618
// 5 20 70 218 585 1155 1993 3176 4794 6951
// 6 27 105 367 1155 3148 6324 11118 18069 27835
// 7 35 149 570 1993 6324 17442 35511 63346 104555
// 8 44 203 838 3176 11118 35511 98857 203412 367103
// 9 54 268 1183 4794 18069 63346 203412 570515 1184040
// 10 65 345 1618 6951 27835 104555 367103 1184040 3341325
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 27ms
memory: 49108kb
input:
3 10 ^>^<^^^^>^ <v^v^^v^v> <>vvvvvvvv 10 1 v ^ < < v < v > < < 5 4 <^^^ <vvv <<^> vv^v <vvv 2 9 ^^^^^^^^^ vvvvvvvvv 9 10 ^>^^<^<^<> <^<<><<<<> v^v^^<>^<^ ^<vvv<><<> <v>>><^v^> ^^^^>^^<<v v^v>v^v^<> v^vvv>v^<^ vvvvv><>v> 8 8 ^^^^<^<^ <>^<v>v^ <v<v>^v> v>v<vv<> ^<^>>v<> <v^v^<<> ^v^^>v<> <vv<vv<> 2 2 ...
output:
5 0 3 8 13 11 0 3 6 9 10 0 10 1 0 7 3 7 3 0 0 3 0 9 11 6 5 6 7 11 4 0 11 11 8 6 3 9 0 16 8 1 9 5 10 4 13 9 7 4 0 14 0 3 4 8 9 19 20 4 0 20 5 6 11 15 13 0 13 0 6 6 3 15 5 14 9 0 2 0 0 11 17 7 1 9 14 12 7 8 0 0 0 10 8 6 6 0 0 13 12 3 12 12 9 18 7 9 5 5 13 7 8 1 12 14 10 5 8 0 0 6 2 11 9 16 7 5 17 0 0 ...
result:
wrong answer 3rd numbers differ - expected: '4', found: '3'