oj.uz

Submission #227665

# Submission time Handle Problem Language Result Execution time Memory
227665 2020-04-28T10:48:26 Z dvdg6566 Dango Maker (JOI18_dango_maker) C++14
13 / 100
 5 ms 384 KB 
#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))break;
		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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Incorrect 4 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Incorrect 4 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -