Submission #227907

#	Time	Username	Problem	Language	Result	Execution time	Memory
227907		dvdg6566	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	648 ms	75444 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 3010;
const ll INF = 1e18;
const ll MOD = 1e9+7;
 
int N,M;
string S;
int done[MAXN][MAXN];
int G[MAXN][MAXN];
ll a;
int dp[MAXN][2];
vi V[MAXN];
int dpmem[MAXN][2];
 
int vert(pi x){
	return G[x.f-1][x.s]==1&&G[x.f+1][x.s]==3;
}
 
int hori(pi x){
	return G[x.f][x.s-1]==1&&G[x.f][x.s+1]==3;
}
 
int ask(int x, int p){
	if(x<0)return -1;
	if(dp[x][p]!=0)return dp[x][p];
	if(dpmem[x][p]!=1)return max(ask(x-1,p),ask(x-2,p^1));
	dp[x][p]=max(ask(x-1,p),ask(x-2,p^1))+1;
	dp[x][p]=max(dp[x][p],1);
	// cout<<x<<' '<<p<<' '<<dp[x][p]<<'\n';
	return dp[x][p];
}
ll ans;
 
int main(){
	cin>>N>>M;
	for (int i=1;i<=N;++i){
		cin>>S;
		for (int j=1;j<=M;++j){
			if(S[j-1]=='R')G[i+1][j+1]=1;
			if(S[j-1]=='G')G[i+1][j+1]=2;
			if(S[j-1]=='W')G[i+1][j+1]=3;			
		}
	}
	for (int i=2;i<=N+1;++i)for(int j=2;j<=M+1;++j){
		if(done[i][j]||G[i][j]!=2)continue;
		int t=1;
		pi cur = mp(i,j);
		if(!vert(cur)&&!hori(cur))continue;
		while(1){
			pi nxt=mp(cur.f+1,cur.s-1);
			done[cur.f][cur.s]=1;
			if(G[nxt.f][nxt.s]!=2)break;
			if(!vert(nxt)&&!hori(nxt))break;
			cur=nxt;++t;
		}
		// cout<<t<<'\n';
		cur=mp(i,j);
		for(int x=0;x<=t;++x)dpmem[x][0]=dpmem[x][1]=dp[x][0]=dp[x][1]=0;
		for (int x=0;x<t;++x){
			pi curr = mp(cur.f+x,cur.s-x);
			if(vert(curr))dpmem[x][0]=1;
			if(hori(curr))dpmem[x][1]=1;
			// cout<<dpmem[x][0]<<' '<<dpmem[x][1]<<'\n';
		}
		ans+=max(ask(t-1,0), ask(t-1,1));
	}
	cout<<ans;
}

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