oj.uz

Submission #237462

# Submission time Handle Problem Language Result Execution time Memory
237462 2020-06-06T17:54:31 Z nikatamliani Miners (IOI07_miners) C++14
100 / 100
 121 ms 100856 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int dp[N][4][4][4][4], ans = 0;
string s;
int diff(int t1, int t2, int t3){
	bool f[4] = {0, 0, 0, 0}; 
	f[t1] = f[t2] = f[t3] = 1;
	return f[1] + f[2] + f[3]; 
}
int main(){
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0][0] = 0;
	int n;
	string s;
	cin >> n >> s;
	s = "@" + s;
	for(int i = 1; i <= n; ++i){
		int t = 1;
		if(s[i] == 'B')t = 2;
		if(s[i] == 'F')t = 3;
		for(int t0 = 0; t0 < 4; ++t0){
			for(int t1 = 0; t1 < 4; ++t1){
				for(int T0 = 0; T0 < 4; ++T0){
					for(int T1 = 0; T1 < 4; ++T1){
						int &dp0 = dp[i][t1][t][T0][T1];
						int &dp1 = dp[i][t0][t1][T1][t];
						int opt = dp[i - 1][t0][t1][T0][T1];
						if(~opt){
							dp0 = max(dp0, opt + diff(t0, t1, t));
							dp1 = max(dp1, opt + diff(T0, T1, t));
						}
					}
				}
			}
		}
	}
	for(int t0 = 0; t0 < 4; ++t0){
		for(int t1 = 0; t1 < 4; ++t1){
			for(int T0 = 0; T0 < 4; ++T0){
				for(int T1 = 0; T1 < 4; ++T1){
					ans = max(ans, dp[n][t0][t1][T0][T1]);
				}
			}
		}
	}
	cout << ans << endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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