Submission #1344558

#TimeUsernameProblemLanguageResultExecution timeMemory
1344558khanhphucscratchDango Maker (JOI18_dango_maker)C++20
100 / 100
272 ms35972 KiB
#include<bits/stdc++.h>
using namespace std;
inline void chmax(int &a, int b)
{
    a = max(a, b);
}
int a[3005][3005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char x; cin>>x;
            if(x == 'R') a[i][j] = 1;
            if(x == 'G') a[i][j] = 2;
            if(x == 'W') a[i][j] = 3;
        }
    }
    int ans = 0;
    for(int s = 2; s <= n+m; s++){
        vector<int> state;
        for(int i = 1; i <= n; i++) if(s-i >= 1 && s-i <= m){
            int r = i, c = s-i, cur = 0;
            if(a[r][c] == 1 && a[r][c+1] == 2 && a[r][c+2] == 3) cur++;
            if(a[r][c] == 1 && a[r+1][c] == 2 && a[r+2][c] == 3) cur += 2;
            state.push_back(cur);
            //cerr<<"A"<<cur<<endl;
        }
        vector<vector<int>> dp(4, vector<int>(state.size()+1));
        for(int j = 0; j < state.size(); j++){
            for(int i = 0; i < 4; i++){
                int ns = (i << 1); if(ns >= 4) ns -= 4;
                chmax(dp[ns][j+1], dp[i][j]);
                if(state[j]%2 == 1 && i == 0) chmax(dp[ns][j+1], dp[i][j]+1);
                if(state[j] >= 2) chmax(dp[ns+1][j+1], dp[i][j]+1);
            }
        }
        int add = 0;
        for(int i = 0; i < 4; i++) add = max(add, dp[i][state.size()]);
        ans += add;
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...