제출 #1333212

#제출 시각아이디문제언어결과실행 시간메모리
1333212WarinchaiDango Maker (JOI18_dango_maker)C++20
33 / 100
199 ms80828 KiB
#include<bits/stdc++.h>
using namespace std;

string s[3005];
int n,m;
int can[3005][3005];
int can2[3005][3005];
int dp[3005][2];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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)if(s[i][j]=='R'&&s[i][j+1]=='G'&&s[i][j+2]=='W')can[i][j]=1;
            if(i+2<n)if(s[i][j]=='R'&&s[i+1][j]=='G'&&s[i+2][j]=='W')can2[i][j]=1;
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        int cur=0;
        for(int j=0;j<=max(n,m);j++)dp[j][0]=dp[j][1]=0;
        for(int x=0,y=i;y>=0;y--,x++){
            cur++;
            dp[cur][0]=dp[cur-1][0];
            if(cur>=3)dp[cur][0]=max(dp[cur][0],dp[cur-3][1]);
            dp[cur][1]=max(dp[cur-1][1],dp[cur-1][0]);
            if(can[x][y])dp[cur][0]++;
            if(can2[x][y])dp[cur][1]++;
        }
        ans+=max(dp[cur][0],dp[cur][1]);
    }
    for(int i=1;i<n;i++){
        int cur=0;
        for(int j=0;j<=max(n,m);j++)dp[j][0]=dp[j][1]=0;
        for(int x=i,y=m-1;y>=0;y--,x++){
            cur++;
            dp[cur][0]=dp[cur-1][0];
            if(cur>=3)dp[cur][0]=max(dp[cur][0],dp[cur-3][1]);
            dp[cur][1]=max(dp[cur-1][1],dp[cur-1][0]);
            if(can[x][y])dp[cur][0]++;
            if(can2[x][y])dp[cur][1]++;
        }
        ans+=max(dp[cur][0],dp[cur][1]);
    }
    cout<<ans<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...