Submission #70211

#	Time	Username	Problem	Language	Result	Execution time	Memory
70211		3zp	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	829 ms	118568 KiB

dango_maker

#include<bits/stdc++.h>
#define maxn 500009
using namespace std;
string s[3009];
bool A[3009][3009];
bool B[3009][3009];
int ans;
int dp[6009][3];
main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(j + 2 < m && s[i][j] == 'R'
                         && s[i][j+1] == 'G'
                         && s[i][j+2] == 'W')
            A[i][j] = 1;
            if(i + 2 < n && s[i][j] == 'R'
                         && s[i+1][j] == 'G'
                         && s[i+2][j] == 'W')
            B[i][j] = 1;
        }
    }
    for(int ipj = 0; ipj < n+m-1; ipj++){
        vector<int> a, b;
        for(int i = 0; i < 3; i++)
            a.push_back(0), b.push_back(0);
        for(int i = n - 1; i >= 0; i--){
            int j = ipj - i;
            if(j < 0 || j >= m) continue;
            a.push_back(A[i][j]);
            b.push_back(B[i][j]);
        }
        int N = a.size();
        for(int i = 3; i < N; i++){
            dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
            if(a[i]) dp[i][1] = dp[i][0] + 1;
            else dp[i][1] = 0;
            if(b[i]) dp[i][2] = max(dp[i-1][2] + 1,
                                        max(dp[i-2][0],dp[i-2][2]) + 1);
            else dp[i][2] = 0;
        }
        ans += max(dp[N - 1][0], max(dp[N - 1][1], dp[N - 1][2]) );
    }
    cout << ans << endl;

}

Compilation message (stderr)

dango_maker.cpp:9:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67