oj.uz

Submission #237463

# Submission time Handle Problem Language Result Execution time Memory
237463 2020-06-06T17:57:52 Z nikatamliani Miners (IOI07_miners) C++14
100 / 100
 108 ms 628 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int dp[2][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[1][t1][t][T0][T1];
						int &dp1 = dp[1][t0][t1][T1][t];
						int opt = dp[0][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){
						dp[0][t0][t1][T0][T1] = dp[1][t0][t1][T0][T1];
						dp[1][t0][t1][T0][T1] = -1;
					}
				}
			}
		}
	}
	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[0][t0][t1][T0][T1]);
				}
			}
		}
	}
	cout << ans << endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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