Submission #432046

#TimeUsernameProblemLanguageResultExecution timeMemory
432046MilosMilutinovicMiners (IOI07_miners)C++14
0 / 100
1585 ms844 KiB
#include <bits/stdc++.h> using namespace std; int dp[2][4][4][4][4]; int count_diff(int x, int y, int z) { set<int> values; if (x != 0) values.insert(x); if (y != 0) values.insert(y); if (z != 0) values.insert(z); return values.size(); } const int inf = 1e9; void clear_dp(int par) { for (int d1 = 0; d1 < 4; d1++) for (int d2 = 0; d2 < 4; d2++) for (int d3 = 0; d3 < 4; d3++) for (int d4 = 0; d4 < 4; d4++) dp[par][d1][d2][d3][d4] = inf; } 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; } int val = A[0]; clear_dp(0); dp[0][A[0]][A[0]][0][0] = 1; dp[0][0][0][A[0]][A[0]] = 1; int curr = 1, prev = 0; for (int i = 1; i < N; i++) { int d = A[i]; clear_dp(curr); for (int d1 = 0; d1 < 4; d1++) for (int d2 = 0; d2 < 4; d2++) for (int d3 = 0; d3 < 4; d3++) for (int d4 = 0; d4 < 4; 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)); } swap(curr, prev); } int answer = 0; for (int d1 = 1; d1 < 4; d1++) for (int d2 = 1; d2 < 4; d2++) for (int d3 = 1; d3 < 4; d3++) for (int d4 = 1; d4 < 4; d4++) answer = max(answer, dp[(N - 1) & 1][d1][d2][d3][d4]); cout << answer; return 0; }

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:42:9: warning: unused variable 'val' [-Wunused-variable]
   42 |     int val = A[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...