Submission #1221237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221237		boclobanchat	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	232 ms	27188 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005;
const int INF=1e9;
int dp[MAXN][8];
string s[MAXN];
bool cka[MAXN][MAXN],ckb[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>s[i];
    	s[i]=' '+s[i];
	}
	for(int i=1;i<=n;i++) for(int j=1;j+2<=m;j++) sum+=(cka[i][j]=(s[i][j]=='R'&&s[i][j+1]=='G'&&s[i][j+2]=='W'));
	for(int i=1;i+2<=n;i++) for(int j=1;j<=m;j++) sum+=(ckb[i][j]=(s[i][j]=='R'&&s[i+1][j]=='G'&&s[i+2][j]=='W'));
	for(int i=2;i+2<=n+m;i++)
	{
		int mx=0;
		for(int j=0;j<8;j++) dp[max(1,i-m)-1][j]=-INF;
		dp[max(1,i-m)-1][0]=0;
		for(int j=max(1,i-m);j<=min(n,i-1);j++)
		{
			for(int k=0;k<8;k++) dp[j][k]=-INF;
			for(int k=0;k<8;k++)
			{
				int v=k%4*2+ckb[j][i-j];
				dp[j][v]=max(dp[j][v],dp[j-1][k]);
				if(cka[j][i-j]) for(int l=0;l<3;l++) if(v&(1<<l)) dp[j][v-(1<<l)]=max(dp[j][v-(1<<l)],dp[j-1][k]+1);
			}
		}
		for(int j=0;j<8;j++) mx=max(mx,dp[min(n,i-1)][j]);
		sum-=mx;
	}
	cout<<sum;
}

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