oj.uz

Submission #892960

# Submission time Handle Problem Language Result Execution time Memory
892960 2023-12-26T09:07:36 Z LCJLY Miners (IOI07_miners) C++14
100 / 100
 68 ms 2852 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2652 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2852 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2652 KB Output is correct