Submission #99688

#	Time	Username	Problem	Language	Result	Execution time	Memory
99688		Bodo171	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	199 ms	91200 KiB

dango_maker

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=3005;
int dp[nmax][nmax][2];
string s[nmax];
int n,m,i,j,ans;
int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("data.in","r",stdin);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=" "+s[i]+" ";
    }
    for(i=1;i<=m+1;i++)
      s[0]+=" ",s[n+1]+=" ";
    for(i=1;i<=n;i++)
        for(j=m;j>=1;j--)
    {
        dp[i][j][0]=max(dp[i-1][j+1][0],dp[i-1][j+1][1]);
        dp[i][j][1]=max(dp[i-1][j+1][0],dp[i-1][j+1][1]);
        if(s[i][j]=='G')
        {
            if(s[i-1][j]=='R'&&s[i+1][j]=='W')  dp[i][j][0]=max(dp[i-1][j+1][0]+1,dp[i][j][0]);
            if(s[i][j-1]=='R'&&s[i][j+1]=='W')  dp[i][j][1]=max(dp[i-1][j+1][1]+1,dp[i][j][1]);
        }
        if(j==1||i==n) ans+=max(dp[i][j][0],dp[i][j][1]);
    }
    cout<<ans;
    return 0;
}

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