oj.uz

Submission #404192

# Submission time Handle Problem Language Result Execution time Memory
404192 2021-05-13T23:35:26 Z Pietra Miners (IOI07_miners) C++14
100 / 100
 1128 ms 145604 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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