Submission #153795

#	Time	Username	Problem	Language	Result	Execution time	Memory
153795		dennisstar	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	459 ms	118392 KiB

dango_maker

#include <bits/stdc++.h>
#define X 5010
int N, M, G[X][X],S[X][X],p,s[X*2],a[X*2];
char C[X][X];
int g()
{
	int i,t=1;
	s[0]=-1;
	for(i=0;i<p;i++){
		if(s[t-1]<a[i])s[t++]=a[i];
		else s[std::lower_bound(s,s+t,a[i])-s]=a[i];
	}
	return t-1;
}
int f()
{
	int i,k,r=0;
	for(k=0;k<N+M-1;k++){
		p=0;
		for(i=std::max(0,k-M+1);i<N&&i<=k;i++){
			if(S[i][k-i])a[p++]=2*i+5;
			if(G[i][k-i])a[p++]=2*i;
		}
		r+=g();
	}
	return r;
}
int main()
{
	scanf("%d%d",&N,&M);
	int i,j;
	for(i=0;i<N;i++) scanf("%s",C[i]);
	for(i=0;i<N;i++) for(j=0;j<M;j++) {
		if(C[i][j]=='R'){
			if(C[i+1][j]=='G'&&C[i+2][j]=='W')S[i][j]=1;
			if(C[i][j+1]=='G'&&C[i][j+2]=='W')G[i][j]=1;
		}
	}
	printf("%d",f());
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:30:7: 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:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<N;i++) scanf("%s",C[i]);
                   ~~~~~^~~~~~~~~~~

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