Submission #1040394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040394		tamir1	Miners (IOI07_miners)	C++17	52 / 100	50 ms	1116 KiB

miners

#include<bits/stdc++.h>
using namespace std;
int n,i,j,ans,x[100005],p,q;
string s;
array<int,3> a,b;
int give(int a,int b,int c){
	int ans=0;
	if(a==1 || b==1 || c==1) ans++;
	if(a==2 || b==2 || c==2) ans++;
	if(a==3 || b==3 || c==3) ans++;
	return ans;
}
array<int,3> split(array<int,3> a,int val){
	return {val,a[0],a[1]};
}
int solve(){
	int i,j,k,ans=0;
	for(i=0;i<(1<<(n-1));i++){
		int cnt=0;
		int a1=0,a2=0,a3=0,b1=0,b2=0,b3=0;
		for(j=0;j<n;j++){
			if(i&(1<<j)){
				a3=a2;
				a2=a1;
				a1=x[j];
				for(k=1;k<=3;k++){
					if(a1==k || a2==k || a3==k) cnt++;
				}
			}
			else{
				b3=b2;
				b2=b1;
				b1=x[j];
				for(k=1;k<=3;k++){
					if(b1==k || b2==k || b3==k) cnt++;
				}
			}
		}
		ans=max(ans,cnt);
	}
	return ans;
}
int main(){
	cin >> n >> s;
	for(i=0;i<n;i++){
		if(s[i]=='M') x[i]=1;
		if(s[i]=='F') x[i]=2;
		if(s[i]=='B') x[i]=3;
	}
	if(n<=20){
		cout << solve();
		return 0;
	}
	for(i=0;i<n;i++){
		if(a[0]==b[0] && a[1]==b[1]){
			a=split(a,x[i]);
			ans+=give(a[0],a[1],a[2]);
			continue;
		}
		p=give(x[i],a[0],a[1]);
		q=give(x[i],b[0],b[1]);
		if(p>q){
			a=split(a,x[i]);
			ans+=p;
			continue;
		}
		if(q>p){
			b=split(b,x[i]);
			ans+=q;
			continue;
		}
		if(p==1){
			ans++;
			if(a[0]==1 && b[0]==1){
				if(a[1]==0) a=split(a,x[i]);
				else b=split(b,x[i]);
			}
			else{
				if(a[0]==0) a=split(a,x[i]);
				else b=split(b,x[i]);
			}
			continue;
		}
		if(p==2){
			ans+=2;
			if(a[0]==b[0] || a[1]==b[1]) a=split(a,x[i]);
			else{
				if(a[0]==x[i]) b=split(b,x[i]);
				else a=split(a,x[i]);
			}
			continue;
		}
		ans+=3;
		a=split(a,x[i]);
	}
	cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8