Submission #645816

#	Time	Username	Problem	Language	Result	Execution time	Memory
645816		ToroTN	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	127 ms	18096 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,m,dp[3005][3],cnt=0,val;
char s[3005][3005];
vector<pair<int,int> > v;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=n;i>=1;i--)
    {
        v.pb({i,1});
    }
    for(int j=2;j<=m;j++)
    {
        v.pb({n,j});
    }
    for(int i=0;i<v.size();i++)
    {
        memset(dp,0,sizeof dp);
        //printf("section %d:%d %d\n",i,v[i].X,v[i].Y);
        for(int x=v[i].X,y=v[i].Y;x>=1&&y<=m;x--,y++)
        {
            //printf("%d %d\n",x,y);
            dp[y][0]=max(dp[y][0],dp[y-1][0]);
            if(y>=3)
            {
                if(s[x][y]=='W'&&s[x][y-1]=='G'&&s[x][y-2]=='R')
                {
                    dp[y][1]=max(dp[y-1][1],dp[y-3][2])+1;
                    dp[y][1]=max(dp[y][1],dp[y-2][1]+1);
                    dp[y][1]=max(dp[y][1],dp[y-3][0]+1);
                }
            }
            if(x>=3)
            {
                if(s[x][y]=='W'&&s[x-1][y]=='G'&&s[x-2][y]=='R')
                {
                    dp[y][2]=max(dp[y-1][2],dp[y-1][1])+1;
                    dp[y][2]=max(dp[y][2],dp[y-1][0]+1);
                }
            }
            dp[y][0]=max(dp[y][0],dp[y][1]);
            dp[y][0]=max(dp[y][0],dp[y][2]);
            val=dp[y][0];
            //printf("%d %d\n",y,dp[y][0]);
        }
        cnt+=val;
    }
    printf("%d\n",cnt);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
dango_maker.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~

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