Submission #1332824

#TimeUsernameProblemLanguageResultExecution timeMemory
1332824AgageldiDango Maker (JOI18_dango_maker)C++20
100 / 100
410 ms102352 KiB
#include <bits/stdc++.h>
using namespace std;

#define N 1000005
#define f first
#define s second

const int inf = INT_MAX;
const int M = 998244353;

int tc = 1, n, dig, m, dp[1000001][3];
char a[3001][3001];
vector <pair<int,int>> v[N];
set <int>s;
bool check(int i,int j,int ok) {
    if(ok == 1) return (i > 1 && a[i - 1][j] == 'R' && a[i][j] == 'G' && i < n && a[i + 1][j] == 'W');
    return (j > 1 && a[i][j - 1] == 'R' && a[i][j] == 'G' && j < m && a[i][j + 1] == 'W');
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    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++) {
            v[i + j].push_back({i, j});
            s.insert(i + j);
        }
    }
    int ans = 0, inx = 0;
    dig = n + m - 1;
    for(auto i : s) {
        int mx = 0;
        inx = 1;
        for(auto j : v[i]) {
            dp[inx][0] = max({dp[inx - 1][0], dp[inx - 1][1], dp[inx - 1][2]});
            for(int k = 1; k <= 2; k++) {
                bool ok = 0;
                if(check(j.first, j.second, k)) ok = 1;
                dp[inx][k] = max({dp[inx - 1][0], dp[inx - 1][k]}) + ok;
                mx = max(mx, dp[inx][k]);
            }
            mx = max(mx,dp[inx][0]);
            inx++;
        }
        ans += mx;
    }
    cout << ans << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...