Submission #892960

#	Time	Username	Problem	Language	Result	Execution time	Memory
892960		LCJLY	Miners (IOI07_miners)	C++14	100 / 100	68 ms	2852 KiB

miners

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

int n;
string s;
int arr[1000005];
int cost[5][5][5];

void solve(){	
	cin >> n >> s;
	
	for(int x=0;x<n;x++){
		if(s[x]=='M') arr[x]=1;
		else if(s[x]=='B') arr[x]=2;
		else arr[x]=3;
	}
	
	for(int x=0;x<=3;x++){
		for(int y=0;y<=3;y++){
			for(int i=0;i<=3;i++){
				set<int>se;
				se.insert(x);
				se.insert(y);
				se.insert(i);
				if(se.find(0)!=se.end()) se.erase(se.find(0));
				cost[x][y][i]=(int)se.size();
			}	
		}
	}
	
	int dp[2][4][4][4][4];
	for(int x=0;x<2;x++){
		for(int x2=0;x2<4;x2++){
			for(int y=0;y<4;y++){
				for(int i=0;i<4;i++){
					for(int z=0;z<4;z++){
						dp[x][x2][y][i][z]=-1e12;
					}
				}
			}
		}
	}
	dp[0][0][0][0][0]=0;
	
	int maxi=0;
	
	
	for(int x=0;x<n;x++){
		maxi=0;
		for(int a=0;a<4;a++){
			for(int a2=0;a2<4;a2++){
				for(int b=0;b<4;b++){
					for(int b2=0;b2<4;b2++){
						int index=arr[x];
						dp[1][index][a][b][b2]=max(dp[0][a][a2][b][b2]+cost[index][a][a2],dp[1][index][a][b][b2]);
						dp[1][a][a2][index][b]=max(dp[0][a][a2][b][b2]+cost[index][b][b2],dp[1][a][a2][index][b]);
					}
				}
			}
		}
		
		for(int a=0;a<4;a++){
			for(int a2=0;a2<4;a2++){
				for(int b=0;b<4;b++){
					for(int b2=0;b2<4;b2++){
						dp[0][a][a2][b][b2]=dp[1][a][a2][b][b2];
						dp[1][a][a2][b][b2]=-1e12;
						maxi=max(maxi,dp[0][a][a2][b][b2]);
					}
				}
			}
		}
	}
	
	cout << maxi;
	
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("in.txt", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}



		


		
		
	

• 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: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8