#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return true;
}
};
const int MN = 3e3+5, MOD = 1e9+7;
char grid[MN][MN]; bool ver[MN][MN], hor[MN][MN]; int dp[MN][MN][3];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
/*
int n, m;
cin >> n >> m;
memset(vis, 0, sizeof vis);
for(int i = 0; i < n+10; i++) for(int j = 0; j < m+10; j++) grid[i][j] = '-';
for(int i = 3; i < n+3; i++) for(int j = 3; j < m+3; j++) cin >> grid[i][j];
vector<pair<int, int>> adj;
for(int i = 3; i < n+3; i++){
for(int j = 3; j < n+3; j++){
if(grid[i][j] == 'R'){
adj.push_back({i, j});
}
}
}
UF uf1, uf2;
for(auto i: adj){
//process the connected components
vector<int>().swap(proc);
if(!vis[i.first][i.second]){
dfs(i);
}
for(auto j: proc){
int x = j[0], y = j[1], dir = j[2];
if(
}
}
*/
int n,m,ret = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> (grid[i] + 1);
for (int j = 1; j <= m-2; j++) if (grid[i][j] == 'R' && grid[i][j+1] == 'G' && grid[i][j+2] == 'W') {
hor[i][j+1] = 1;
}
}
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n-2; i++) if (grid[i][j] == 'R' && grid[i+1][j] == 'G' && grid[i+2][j] == 'W')
ver[i+1][j] = 1;
for (int v = 2, add = 0; v <= n+m; v++, ret += add, add = 0)
for (int i = 1, j = v - i; i <= n; i++)
if (1 <= j && j <= m) {
dp[i][j][0] = max({dp[i-1][j+1][0],dp[i-1][j+1][1],dp[i-1][j+1][2]});
if (hor[i][j])
dp[i][j][1] = max(dp[i-1][j+1][0],dp[i-1][j+1][1]) + 1;
if (ver[i][j])
dp[i][j][2] = max(dp[i-1][j+1][0],dp[i-1][j+1][2]) + 1;
add = max({add,dp[i][j][0],dp[i][j][1],dp[i][j][2]});
}
cout << ret << '\n';
return 0;
}
Compilation message
dango_maker.cpp: In function 'void usaco(std::string)':
dango_maker.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
13 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
14 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |