Submission #941034

#	Time	Username	Problem	Language	Result	Execution time	Memory
941034		carriewang	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	150 ms	18100 KiB

dango_maker

#include <bits/stdc++.h>
#define ll longlong
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) x.szie()
#define all(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
const int maxn=3005;
int n,m,dp[3][maxn];
char c[maxn][maxn];
int 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 >> c[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n+m;i++){
        int ret=0;
        memset(dp,0,sizeof(dp));
        for(int x=1,y=i-1;x<=n;x++,y--){
            if(y>m) continue;
            if(y<1) break;
            dp[0][x]=max(dp[0][x-1],max(dp[1][x-1],dp[2][x-1]));
            if(c[x][y]!='G') continue;
            if(c[x][y-1]=='R' && c[x][y+1]=='W'){
                dp[1][x]=max(dp[0][x-1],dp[1][x-1])+1;
            }
            if(c[x-1][y]=='R' && c[x+1][y]=='W'){
                dp[2][x]=max(dp[0][x-1],dp[2][x-1])+1;
            }
            ret=max(max(ret,dp[0][x]),max(dp[1][x],dp[2][x]));
        }
        ans+=ret;
    }
    cout << ans << "\n";
}

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