Submission #331785

#	Time	Username	Problem	Language	Result	Execution time	Memory
331785		daniel920712	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	865 ms	238956 KiB

dango_maker

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;
char all[3005][3005];
bool have[3005][3005][5]={0};
int DP[3005][3005][5]={0};


int ans=0,a,b,N,M;
int F(int x,int y,int z)
{
    if(x>=N||y<0) return 0;
    if(have[x][y][z]) return DP[x][y][z];
    have[x][y][z]=1;
    DP[x][y][z]=F(x+1,y-1,min(z+1,3));
    if(y+2<M&&z==3&&all[x][y]=='R'&&all[x][y+1]=='G'&&all[x][y+2]=='W') DP[x][y][z]=max(DP[x][y][z],F(x+1,y-1,min(z+1,3))+1);
    if(x+2<N&&all[x][y]=='R'&&all[x+1][y]=='G'&&all[x+2][y]=='W') DP[x][y][z]=max(DP[x][y][z],F(x+1,y-1,1)+1);
    return DP[x][y][z];
}
int main()
{
    int i,j;
    scanf("%d %d",&N,&M);
    for(i=0;i<N;i++) scanf("%s",all[i]);
    for(i=0;i<M;i++) ans+=F(0,i,3);
    for(i=1;i<N;i++) ans+=F(i,M-1,3);
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:29:11: warning: unused variable 'j' [-Wunused-variable]
   29 |     int i,j;
      |           ^
dango_maker.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:31:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     for(i=0;i<N;i++) scanf("%s",all[i]);
      |                      ~~~~~^~~~~~~~~~~~~

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