oj.uz

Submission #535857

# Submission time Handle Problem Language Result Execution time Memory
535857 2022-03-11T14:40:34 Z cig32 Miners (IOI07_miners) C++17
100 / 100
 198 ms 109032 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
string s;
int n;
int c(int a,int b,int c){
	int sol = 0;
	if (a == 1 || b == 1 || c == 1) sol++;
	if (a == 2 || b == 2 || c == 2) sol++;
	if (a == 3 || b == 3 || c == 3) sol++;
	return sol;
}
 
int a[N];
int dp[N][4][4][4][4];
 
int solve(int idx,int prea1,int prea2,int preb1,int preb2){
	if(idx==n) {
		return 0;
	}
	int &ans=dp[idx][prea1][prea2][preb1][preb2];
	if(ans!=-1) return ans;
	int choice1=solve(idx+1,a[idx],prea1,preb1,preb2)+c(a[idx],prea1,prea2);
	int choice2=solve(idx+1,prea1,prea2,a[idx],preb1)+c(a[idx],preb1,preb2);
	return ans=max(choice1,choice2);
}
int main()
{
 
	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n;
 
	cin>>s;
	for(int i=0; i<n; i++) {
		if(s[i]=='B') {
			a[i]=3;
		}
		else if(s[i]=='M') {
			a[i]=1;
		}
		else{
			a[i]=2;
		}
	}
 
	memset(dp,-1,sizeof dp);
	int ans=solve(0,0,0,0,0);
	cout<<ans<<endl;
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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