Submission #41262

#	Time	Username	Problem	Language	Result	Execution time	Memory
41262		Kerim	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	933 ms	121388 KiB

dango_maker

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N=3e3+6;
int mask[N][N],dp[N][3],n,m;
char arr[N][N];
int rec(int xx,int yy,int pos,int last){
	int x=xx+pos,y=yy-pos;
	if(x<0 or y<0 or x>=n or y>=m)
		return 0;
	int &ret=dp[pos][last];
	if(~ret)
		return ret;ret=rec(xx,yy,pos+1,0);
	if(!mask[x][y])
		return ret;
	else if(mask[x][y]==1){
		if(last!=2)
			umax(ret,rec(xx,yy,pos+1,1)+1);
		return ret;
	}	
	else if(mask[x][y]==2){
		if(last!=1)
			umax(ret,rec(xx,yy,pos+1,2)+1);
		return ret;
	}
	if(last!=1)
		umax(ret,rec(xx,yy,pos+1,2)+1);
	if(last!=2)
		umax(ret,rec(xx,yy,pos+1,1)+1);
	return ret;		
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf(" %c",&arr[i][j]);
	for(int i=0;i<n;i++)	
		for(int j=0;j<m;j++)
			if(arr[i][j]=='G'){
				if(j>0 and j+1<m and arr[i][j-1]=='R' and arr[i][j+1]=='W')
					mask[i][j]|=1;
				if(i>0 and i+1<n and arr[i-1][j]=='R' and arr[i+1][j]=='W')
					mask[i][j]|=2;
			}
	int ans=0;	
	for(int i=0;i<m;i++){
		memset(dp,-1,sizeof dp);
		ans+=rec(0,i,0,0);
	}
	for(int i=1;i<n;i++){
		memset(dp,-1,sizeof dp);
		ans+=rec(i,m-1,0,0);
	}
	printf("%d\n",ans);	
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:50:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
dango_maker.cpp:53:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&arr[i][j]);
                           ^

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