QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648982 | #3125. Dango Maker | Dimash | 0 | 1ms | 5932kb | C++17 | 1.6kb | 2024-10-17 21:11:12 | 2024-10-17 21:11:13 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e3 + 12, MOD = 998244353, M = 3e6 + 12;
char a[N][N];
int n, m, ok[N][N][2], dp[N * 2][3];
vector<array<int, 2>> e[N * 2];
void test() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == 'G' && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') {
ok[i][j][0] = 1;
}
if(a[i][j] == 'G' && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') {
ok[i][j][1] = 1;
}
e[i + j].push_back({i, j});
}
}
int res = 0;
for(int i = 1; i <= n + m; i++) {
int f = (int)e[i].size() - 1;
if(e[i].empty()) continue;
dp[0][0] = ok[e[i][0][0]][e[i][0][1]][0];
dp[0][1] = ok[e[i][0][0]][e[i][0][1]][1];
dp[0][2] = 0;
for(int j = 1; j < (int)e[i].size(); j++) {
int x = e[i][j][0], y = e[i][j][1];
dp[j][2] = max({dp[j - 1][0], dp[j - 1][1], dp[j - 1][2]});
dp[j][0] = max(dp[j - 1][1], dp[j - 1][2]) + ok[x][y][0];
dp[j][1] = max(dp[j - 1][0], dp[j - 1][2]) + ok[x][y][1];
}
res += max({dp[f][0], dp[f][1], dp[f][2]});
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 13
Accepted
time: 0ms
memory: 5856kb
input:
1 1 G
output:
0
result:
ok single line: '0'
Test #2:
score: 13
Accepted
time: 1ms
memory: 5776kb
input:
1 2 RG
output:
0
result:
ok single line: '0'
Test #3:
score: 13
Accepted
time: 0ms
memory: 5924kb
input:
2 1 W R
output:
0
result:
ok single line: '0'
Test #4:
score: 13
Accepted
time: 0ms
memory: 5840kb
input:
3 2 WW RW WR
output:
0
result:
ok single line: '0'
Test #5:
score: 13
Accepted
time: 0ms
memory: 5872kb
input:
4 4 GRRW GWWR WWWW RGRG
output:
0
result:
ok single line: '0'
Test #6:
score: 13
Accepted
time: 0ms
memory: 5932kb
input:
4 4 RGRR RRRG GRGW RGWW
output:
2
result:
ok single line: '2'
Test #7:
score: 13
Accepted
time: 0ms
memory: 5860kb
input:
4 4 RRGR GRRG WRGW RGWW
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 5812kb
input:
4 4 RGWR GGGW WWGW RWGW
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%