oj.uz

Submission #618826

# Submission time Handle Problem Language Result Execution time Memory
618826 2022-08-02T07:46:21 Z 1ne Miners (IOI07_miners) C++14
100 / 100
 231 ms 116452 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	string s;cin>>s;
	auto getid = [&](char u){
		if (u == 'M')return 1;
		else if (u == 'B')return 2;
		return 3;
	};
	int dp[n][4][4][4][4];
	for (int i = 0;i<n;++i){
		for (int j = 0;j<4;++j){
			for (int k = 0;k<4;++k){
				for (int l = 0;l<4;++l){
					for (int m = 0;m<4;++m){
						dp[i][j][k][l][m] = -1;
					}
				}
			}
		}
	}
	function<int(int,int,int,int,int)>solve = [&](int u,int prev,int prev2,int prev3,int prev4){
		if (u == n)return 0;
		if (dp[u][prev][prev2][prev3][prev4]!=-1)return dp[u][prev][prev2][prev3][prev4];
		int temp = getid(s[u]);
		int cnts = 0,cnts2 = 0;
		if (prev != 0)cnts++;
		if (prev2 != 0 && prev2!=prev)cnts++;
		if (temp!=prev && temp!=prev2)cnts++;
		if (prev3 != 0)cnts2++;
		if (prev4 != 0 && prev4!=prev3)cnts2++;
		if (temp!=prev3 && temp!=prev4)cnts2++;
		long long ans = max(solve(u + 1,prev2,temp,prev3,prev4) + cnts , solve(u + 1,prev,prev2,prev4,temp) + cnts2);
		return dp[u][prev][prev2][prev3][prev4] = ans; 
	};
	cout<<solve(0,0,0,0,0)<<'\n';
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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