Submission #432790

#TimeUsernameProblemLanguageResultExecution timeMemory
432790tengiz05Miners (IOI07_miners)C++17
100 / 100
386 ms101184 KiB
#include <bits/stdc++.h> constexpr int N = 100000; int dp[N][4][4][4][4]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::string s; std::cin >> s; std::vector<int> a(n); for (int i = 0; i < n; i++) { a[i] = std::string("MFB").find(s[i]) + 1; } memset(dp, 190, sizeof dp); dp[0][0][a[0]][0][0] = 1; dp[0][0][0][0][a[0]] = 1; for (int p = 1; p < n; p++) { for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) for (int I = 0; I < 4; I++) for (int J = 0; J < 4; J++) dp[p][i][j][I][J] = dp[p - 1][i][j][I][J]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { for (int I = 0; I < 4; I++) { for (int J = 0; J < 4; J++) { int cost; if (i == 0 && j == 0) cost = 1; else if (i == 0 || j == 0) cost = 1 + ((i ^ j) != a[p]); else if (i == j && j == a[p]) cost = 1; else if (i == j || j == a[p] || i == a[p]) cost = 2; else cost = 3; dp[p][j][a[p]][I][J] = std::max(dp[p][j][a[p]][I][J], dp[p - 1][i][j][I][J] + cost); if (I == 0 && J == 0) cost = 1; else if (I == 0 || J == 0) cost = 1 + ((I ^ J) != a[p]); else if (I == J && J == a[p]) cost = 1; else if (I == J || J == a[p] || I == a[p]) cost = 2; else cost = 3; dp[p][i][j][J][a[p]] = std::max(dp[p][i][j][J][a[p]], dp[p - 1][i][j][I][J] + cost); } } } } } int ans = 0; for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) for (int I = 0; I < 4; I++) for (int J = 0; J < 4; J++) ans = std::max(ans, dp[n - 1][i][j][I][J]); std::cout << ans << "\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...