Submission #227527

#	Time	Username	Problem	Language	Result	Execution time	Memory
227527		kshitij_sodani	Trobojnica (COCI19_trobojnica)	C++17	0 / 110	11 ms	12160 KiB

trobojnica

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
int it[200001];
int dp[1001][1001][3];
//0 add to first 
//1 add to second
int n;
int find(int aa,int bb,int cc){
	if(dp[aa][bb][cc]>-1){
		return dp[aa][bb][cc];
	}
	if(bb==(aa+1)%n){
		dp[aa][bb][cc]=1;
		return 1;
	}
	if(aa==bb){
		dp[aa][bb][cc]=1;
		return 1;
	}
//	cout<<aa<<" "<<bb<<" "<<cc<<endl;
	if(bb==(aa+2)%n){
		if(it[aa]==it[(aa+1)%n] or it[(aa+1)%n]==cc or it[aa]==cc){
			dp[aa][bb][cc]=0;
			return 0;
		}
	//	cout<<aa<<","<<bb<<","<<cc<<endl;
		dp[aa][bb][cc]=1;
		return 1;
	}
	dp[aa][bb][cc]=0;
		int ee=(bb-1);
		if(ee<0){
			ee+=n;
		}
		for(int i=0;i<3;i++){
			if(i==it[ee] or i==cc or it[ee]==cc){
				continue;
			}
			dp[aa][bb][cc]=max(find(aa,ee,i),dp[aa][bb][cc]);
		}
		int ff=(aa+1);
		if(ff>=n){
			ff-=n;
		}
		for(int i=0;i<3;i++){
			if(i==it[aa] or i==cc or it[aa]==cc){
				continue;
			}
			dp[aa][bb][cc]=max(find(ff,bb,i),dp[aa][bb][cc]);
		}
	return dp[aa][bb][cc];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	memset(dp,-1,sizeof(dp));
	char s;
	for(int i=0;i<n;i++){
		cin>>s;
		if(s=='1'){
			it[i]=0;
		}
		else if(s=='2'){
			it[i]=1;
		}
		else{
			it[i]=2;
		}
	}

	int ans=0;
	for(int i=0;i<n;i++){
		//cout<<find(i,(i-1+n)%n,it[(i-1+n)%n])<<endl;
		ans=max(ans,find(i,(i-1+n)%n,it[(i-1+n)%n]));
		
	}
	if(ans==0){
		cout<<"NE"<<endl;
	}
	else{
		cout<<"DA"<<endl;
	}







	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50