Submission #404192

#	Time	Username	Problem	Language	Result	Execution time	Memory
404192		Pietra	Miners (IOI07_miners)	C++14	100 / 100	1128 ms	145604 KiB

miners

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

const int maxn = 1e5 + 5 ; 

int n, dp[maxn][4][4][4][4], v[maxn] ; 
string s ; 

int solve(int i, int t11, int t12, int t21, int t22){ // os ultimos 2 importam qd add o novo 

	if(i >= n) return 0 ; 

	if(dp[i][t11][t12][t21][t22] != -1) return dp[i][t11][t12][t21][t22] ; 

	set<int> ans1, ans2 ;

	if(t11 != 0) ans1.insert(t11) ; 
	if(t12 != 0) ans1.insert(t12) ; 
	//qto ganha ao add na mina 1 ou na 2 (qts diferentes tiver)
	ans1.insert(v[i]) ; 
	ans2.insert(v[i]) ; 

	if(t21 != 0) ans2.insert(t21) ; 
	if(t22 != 0) ans2.insert(t22) ; 

	return dp[i][t11][t12][t21][t22] = max(ans1.size() + solve(i+1, v[i], t11, t21, t22), ans2.size() + solve(i+1, t11, t12, v[i], t21)) ; 
    //mlr colocar o atual em 1 ou 2?
}

int main(){

	cin >> n ; 
	cin >> s ; 

	memset(dp, -1, sizeof dp) ; 

	for(int i = 0 ; i < n ; i++){
		if(s[i] == 'M') v[i] = 1 ; 
		else if(s[i] == 'B') v[i] = 2 ; 
		else v[i] = 3 ; 
	}

	cout << solve(0, 0, 0, 0, 0) << "\n" ;

}

• 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