Submission #1127070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127070		sitablechair	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	373 ms	9388 KiB

dango_maker

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=3003;

char c[N][N];
int n,m,mmb[N*2];
int dp[N][3][3];

inline bool down(int x,int y) {
    if (x+2>n || y>m) return 0;
    return (c[x][y]=='R'&&c[x+1][y]=='G'&&c[x+2][y]=='W');
}
inline bool right(int x,int y) {
    if (x>n || y+2>m) return 0;
    return (c[x][y]=='R'&&c[x][y+1]=='G'&&c[x][y+2]=='W');
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    For(i,1,n) 
        For(j,1,m) cin >> c[i][j];
    For(i,1,n)
        For(j,1,m) mmb[i+j]=max(mmb[i+j],j);
    ll ans=0;
    For(i,2,n+m-2) {
        For(j,1,mmb[i]) 
            For(k,0,2)
                For(l,0,2) dp[j][k][l]=-1e9;
        
        dp[mmb[i]][0][0]=0;
        if(down(i-mmb[i],mmb[i])) dp[mmb[i]][2][0]=1;
        if (right(i-mmb[i],mmb[i])) dp[mmb[i]][0][0]=1; 
        ForD(j,mmb[i],2) 
            For(k,0,2)
                For(l,0,2) {
                    if (dp[j][k][l]<=-1e9) continue;
                    dp[j-1][0][max(k-1,0)]=max(dp[j-1][0][max(k-1,0)],dp[j][k][l]);
                    if (k==0 && l==0 && right(i-j+1,j-1)) dp[j-1][0][0]=max(dp[j-1][0][0],dp[j][k][l]+1);
                    if (down(i-j+1,j-1)) dp[j-1][2][max(k-1,0)]=max(dp[j-1][2][max(k-1,0)],dp[j][k][l]+1);
                }
        // if (i==5) debug(down(4,1),dp[mmb[i]][2][0]);
        
        int cur=0;
        For(i,0,2) 
            For(j,0,2) cur=max(cur,dp[1][i][j]);
        ans+=cur;
    }   
    cout << ans;
    return 0; 
}

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