// author: gary
// created: 2018/09/04 09:19:17
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits>
#include <utility>
#include <functional>
#include <string>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define ALL(c) (c).begin(), (c).end()
#define CNT(c, x) ((c).find(x) != (c).end())
typedef pair<int, int> pii;
typedef long long ll;
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
const int N = 3005;
int n, m;
char G[N][N];
int get(int i, int j) {
return i >= 0 && i < n && j >= 0 && j < m ? G[i][j] : 'X';
}
int down(int i, int j) {
return get(i, j) == 'R' && get(i+1,j) == 'G' && get(i+2,j) == 'W';
}
int right(int i, int j) {
return get(i, j) == 'R' && get(i,j+1) == 'G' && get(i,j+2) == 'W';
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%s", G[i]);
}
// for(int i = 0; i < n; i++) { printf("%d\n", right(i, 0)); }
int ans = 0;
for(int ij = 0; ij < n+m-1; ij++) {
// 0 ... right , 1 ... down
int dp[2][2] = {}; // ij-2, ij-1
int mx = 0;
deque<int> prev;
for(int i = 0; i < n; i++) {
int j = ij - i;
if(j < 0 || j >= m || get(i, j) != 'R') {
continue;
}
int nx[2][2] = {};
int touch2 = SZ(prev) == 2 && prev.front() + 2 == i;
int touch1 = SZ(prev) >= 1 && prev.back() + 1 == i;
// Calc
for(int d2 = 0; d2 < 2; d2++) {
for(int d1 = 0; d1 < 2; d1++) {
if(!(d1 && touch1) && !(d2 && touch2)) {
cmax(nx[d1][0], dp[d2][d1] + right(i, j));
}
cmax(nx[d1][1], dp[d2][d1] + down(i, j));
}
}
// Copy
for(int d2 = 0; d2 < 2; d2++) {
for(int d1 = 0; d1 < 2; d1++) {
dp[d2][d1] = nx[d2][d1];
cmax(mx, dp[d2][d1]);
}
}
while(SZ(prev) == 2) {
prev.pop_front();
}
prev.emplace_back(i);
}
// printf("ij=%d mx=%d\n", ij, mx);
ans += mx;
}
printf("%d\n", ans);
return 0;
}
Compilation message
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", G[i]);
~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
544 KB |
Output is correct |
5 |
Correct |
2 ms |
556 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
748 KB |
Output is correct |
9 |
Correct |
2 ms |
748 KB |
Output is correct |
10 |
Correct |
2 ms |
748 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
544 KB |
Output is correct |
5 |
Correct |
2 ms |
556 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
748 KB |
Output is correct |
9 |
Correct |
2 ms |
748 KB |
Output is correct |
10 |
Correct |
2 ms |
748 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
544 KB |
Output is correct |
5 |
Correct |
2 ms |
556 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
616 KB |
Output is correct |
8 |
Correct |
2 ms |
748 KB |
Output is correct |
9 |
Correct |
2 ms |
748 KB |
Output is correct |
10 |
Correct |
2 ms |
748 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Incorrect |
2 ms |
748 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |