Submission #939710

#TimeUsernameProblemLanguageResultExecution timeMemory
939710mansurDango Maker (JOI18_dango_maker)C++17
100 / 100
218 ms87948 KiB
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #include<bits/stdc++.h> using namespace std; #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) (int)a.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; const int N = 1e6 + 1, mod = 1e9 + 7; const ll inf = 1e18; double eps = 1e-15; bool flg = 0; void slv() { int n, m; cin >> n >> m; char c[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> c[i][j]; } } int dp[n + 1][m + 1][2], mx[n + m + 1]; memset(dp, 0, sizeof(dp)); memset(mx, 0, sizeof(mx)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int v = max(dp[i][j][0], dp[i][j][1]); mx[i + j] = max(mx[i + j], v); if (i < n && j > 1) { dp[i + 1][j - 1][0] = max(dp[i + 1][j - 1][0], dp[i][j][0]); dp[i + 1][j - 1][1] = max(dp[i + 1][j - 1][1], dp[i][j][1]); } if (j + 2 <= m && c[i][j] == 'R' && c[i][j + 1] == 'G' && c[i][j + 2] == 'W') { if (i < n && j > 1) { dp[i + 1][j - 1][0] = max(dp[i + 1][j - 1][0], dp[i][j][0] + 1); dp[i + 1][j - 1][1] = max(dp[i + 1][j - 1][1], dp[i][j][0] + 1); } mx[i + j] = max(mx[i + j], dp[i][j][0] + 1); } if (i + 2 <= n && c[i][j] == 'R' && c[i + 1][j] == 'G' && c[i + 2][j] == 'W') { if (j > 3 && i + 3 <= n) dp[i + 3][j - 3][0] = max(dp[i + 3][j - 3][0], dp[i][j][1] + 1); if (i < n && j > 1) dp[i + 1][j - 1][1] = max(dp[i + 1][j - 1][1], dp[i][j][1] + 1); mx[i + j] = max(mx[i + j], dp[i][j][1] + 1); } } } int ans = 0; for (int i = 1; i <= n + m; i++) { //cout << mx[i] << ' '; ans += mx[i]; } cout << ans; } main() { //freopen("rsq.in", "r", stdin); //freopen("rsq.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int tp = 1; if (flg) cin >> tp; while (tp--) { //cout << "Case #" << cur++ << ": "; slv(); } } //wenomechainsama

Compilation message (stderr)

dango_maker.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...