Submission #432034

#TimeUsernameProblemLanguageResultExecution timeMemory
432034MilosMilutinovicMiners (IOI07_miners)C++14
84 / 100
1595 ms844 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; string S; cin >> S; vector<int> A(N); for (int i = 0; i < N; i++) { if (S[i] == 'M') A[i] = 1; if (S[i] == 'F') A[i] = 2; if (S[i] == 'B') A[i] = 3; } auto count_diff = [&](int x, int y, int z) -> int { set<int> values; if (x != 0) values.insert(x); if (y != 0) values.insert(y); if (z != 0) values.insert(z); return (int) values.size(); }; int dp[2][4][4][4][4], val = A[0]; auto clear_dp = [&](int par) -> void { for (int d1 = 0; d1 <= 3; d1++) for (int d2 = 0; d2 <= 3; d2++) for (int d3 = 0; d3 <= 3; d3++) for (int d4 = 0; d4 <= 3; d4++) dp[par][d1][d2][d3][d4] = -1e9; }; clear_dp(0); dp[0][val][val][0][0] = 1; dp[0][0][0][val][val] = 1; for (int i = 1; i < N; i++) { int curr = i & 1, prev = curr ^ 1, d = A[i]; clear_dp(curr); for (int d1 = 0; d1 <= 3; d1++) for (int d2 = 0; d2 <= 3; d2++) for (int d3 = 0; d3 <= 3; d3++) for (int d4 = 0; d4 <= 3; d4++) { dp[curr][d][d1][d3][d4] = max(dp[curr][d][d1][d3][d4], dp[prev][d1][d2][d3][d4] + count_diff(d, d1, d2)); dp[curr][d1][d2][d][d3] = max(dp[curr][d1][d2][d][d3], dp[prev][d1][d2][d3][d4] + count_diff(d, d3, d4)); } } int answer = 0; for (int d1 = 1; d1 <= 3; d1++) for (int d2 = 1; d2 <= 3; d2++) for (int d3 = 1; d3 <= 3; d3++) for (int d4 = 1; d4 <= 3; d4++) answer = max(answer, dp[(N - 1) & 1][d1][d2][d3][d4]); cout << answer << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...