#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
/*
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define dauzhan gay
#define popcount __builtin_popcount
const long double Eps = 1e-12;
const int max1 = 1e9 + 100;
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 2e5 + 100;
const int B = 9000000 + 1;
const ll INF = 1e18 + 100;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
if(y < 0) return 0;
if(y == 0) return 1;
if(y == 1) return x;
if(y % 2 == 0) {
ll now = binpow(x,y/2,md);
return (1ll*now*now) % md;
}
else {
ll now = binpow(x,y/2,md);
return (1ll*((1ll*now*now) % md)*x) % md;
}
}
/*
for(int i = 1;i <= n;i++) sp[0][i] = a[i];
for(int i = 1;i <= log2(n);i++) {
for(int l = 1;l <= n;l++) {
int r = l + (1 << i) - 1;
if(r > n) break;
int middle = l + (1 << (i - 1));
sp[i][l] = max(sp[i - 1][l],sp[i - 1][middle]);
}
}
int get(int l,int r) {
int g = log2(r - l + 1);
return max(sp[g][l],sp[g][r - (1 << g) + 1]);
}
*/
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
char a[n + 1][m + 1];
bool was[n + 1][m + 1];
bool check[n + 1][m + 1][2];
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
cin >> a[i][j];
was[i][j] = false;
check[i][j][0] = false;
check[i][j][1] = false;
}
}
int ans = 0;
for(int i = 1;i <= n + m;i++) {
if(i == m + 1) continue;
vector <pair <int,int> > v;
if(i <= m) {
int x = 1,y = i;
while(x >= 1&&x <= n&&y >= 1&&y <= m) {
v.pb({x,y});
x++;
y--;
}
}
else {
int x = i - m,y = m;
while(x >= 1&&x <= n&&y >= 1&&y <= m) {
v.pb({x,y});
x++;
y--;
}
}
v.pb({1,1});
reverse(all(v));
int len = sz(v) - 1;
int dp[len + 2][3];
for(int i = 0;i <= len + 1;i++) {
for(int j = 0;j < 3;j++) {
dp[i][j] = min1;
}
}
dp[1][0] = 0;
for(int i = 1;i <= len;i++) {
for(int j = 0;j < 3;j++) {
if(j != 0) dp[i + 1][j - 1] = max(dp[i + 1][j - 1],dp[i][j]);
dp[i + 1][0] = max(dp[i + 1][0],dp[i][0]);
int nowx = v[i].f,nowy = v[i].s;
if(a[nowx][nowy] != 'W') continue;
if(nowx > 2&&a[nowx - 1][nowy] == 'G'&&a[nowx - 2][nowy] == 'R') {
dp[i + 1][2] = max(dp[i + 1][2],dp[i][j] + 1);
}
if(j == 0) {
if(nowy > 2&&a[nowx][nowy - 1] == 'G'&&a[nowx][nowy - 2] == 'R') {
dp[i + 1][0] = max(dp[i + 1][0],dp[i][j] + 1);
}
}
}
}
ans+=max({dp[len + 1][0],dp[len + 1][1],dp[len + 1][2]});
//cout << dp[len + 1][0] << endl;
}
cout << ans << endl;
}
Compilation message
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:116:10: warning: variable 'was' set but not used [-Wunused-but-set-variable]
116 | bool was[n + 1][m + 1];
| ^~~
dango_maker.cpp:117:10: warning: variable 'check' set but not used [-Wunused-but-set-variable]
117 | bool check[n + 1][m + 1][2];
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
356 KB |
Output is correct |
37 |
Correct |
0 ms |
600 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
0 ms |
348 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
0 ms |
544 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
356 KB |
Output is correct |
37 |
Correct |
0 ms |
600 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
0 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
0 ms |
348 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
0 ms |
544 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
0 ms |
348 KB |
Output is correct |
54 |
Correct |
1 ms |
348 KB |
Output is correct |
55 |
Correct |
1 ms |
344 KB |
Output is correct |
56 |
Correct |
1 ms |
348 KB |
Output is correct |
57 |
Correct |
1 ms |
464 KB |
Output is correct |
58 |
Correct |
24 ms |
5008 KB |
Output is correct |
59 |
Correct |
211 ms |
40380 KB |
Output is correct |
60 |
Correct |
209 ms |
40276 KB |
Output is correct |
61 |
Correct |
214 ms |
40340 KB |
Output is correct |
62 |
Correct |
1 ms |
348 KB |
Output is correct |
63 |
Correct |
204 ms |
39028 KB |
Output is correct |
64 |
Correct |
174 ms |
40376 KB |
Output is correct |
65 |
Correct |
168 ms |
40316 KB |
Output is correct |
66 |
Correct |
175 ms |
40284 KB |
Output is correct |
67 |
Correct |
171 ms |
40276 KB |
Output is correct |
68 |
Correct |
170 ms |
40176 KB |
Output is correct |
69 |
Correct |
173 ms |
40380 KB |
Output is correct |
70 |
Correct |
23 ms |
4956 KB |
Output is correct |
71 |
Correct |
19 ms |
4956 KB |
Output is correct |
72 |
Correct |
19 ms |
4956 KB |
Output is correct |
73 |
Correct |
22 ms |
5136 KB |
Output is correct |
74 |
Correct |
19 ms |
4952 KB |
Output is correct |
75 |
Correct |
19 ms |
4956 KB |
Output is correct |
76 |
Correct |
19 ms |
4956 KB |
Output is correct |
77 |
Correct |
19 ms |
4956 KB |
Output is correct |
78 |
Correct |
24 ms |
5144 KB |
Output is correct |
79 |
Correct |
19 ms |
4956 KB |
Output is correct |
80 |
Correct |
20 ms |
4956 KB |
Output is correct |
81 |
Correct |
19 ms |
5064 KB |
Output is correct |
82 |
Correct |
19 ms |
4956 KB |
Output is correct |
83 |
Correct |
19 ms |
4956 KB |
Output is correct |
84 |
Correct |
20 ms |
5140 KB |
Output is correct |
85 |
Correct |
20 ms |
4956 KB |
Output is correct |
86 |
Correct |
19 ms |
4956 KB |
Output is correct |
87 |
Correct |
20 ms |
5016 KB |
Output is correct |
88 |
Correct |
19 ms |
5132 KB |
Output is correct |
89 |
Correct |
22 ms |
5212 KB |
Output is correct |
90 |
Correct |
20 ms |
4956 KB |
Output is correct |