Submission #1153463

#TimeUsernameProblemLanguageResultExecution timeMemory
1153463spycoderytDango Maker (JOI18_dango_maker)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
int A[N][N],dp[N][N];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            char c;
            cin>>c;
            if(c=='R')A[i][j]=1;
            else if (c == 'G') A[i][j] = 2;
            else A[i][j] = 3;
        }
    }
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            // drag 
            // dp[i][j]=min(dp[i][j],1);
            // dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
            // hor
            int h1 = (A[i][j] == 1 && A[i][j+1] == 2 && A[i][j+2] == 3);
            int h2 = (A[i+1][j] == 1 && A[i+1][j+1] == 2 && A[i+1][j+2] == 3);
            int h3 = (A[i+2][j] == 1 && A[i+2][j+1] == 2 && A[i+2][j+2] == 3);
            int v1 = (A[i][j] == 1 && A[i+1][j] == 2 && A[i+2][j] == 3);
            int v2 = (A[i][j+1] == 1 && A[i+1][j+1] == 2 && A[i+2][j+1] == 3);
            int v3 = (A[i][j+2] == 1 && A[i+1][j+2] == 2 && A[i+2][j+2] == 3);
            if(h1)dp[i][j+2]++;
            if(v1)dp[i+2][j]++;
            dp[i+2][j+2] -= (h1 + h2 + h3) * (v1 + v2 + v3);
        }
    }

    // for(int i = 1;i<=n;i++) {
    //     for(int j = 1;j<=m;j++) {
    //         cerr << dp[i][j] << " ";
    //     }cerr << "\n";
    // }
    for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) {
        dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
    }
    // for(int i = 1;i<=n;i++) {
    //     for(int j = 1;j<=m;j++) {
    //         cout << dp[i][j] << " ";
    //     }cout << "\n";
    // }
    cout<<dp[n][m];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...