Submission #432027

#TimeUsernameProblemLanguageResultExecution timeMemory
432027MilosMilutinovicMiners (IOI07_miners)C++14
84 / 100
1585 ms588 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; auto get_val = [&](char c) -> int { if (c == 'M') return 1; if (c == 'F') return 2; if (c == 'B') return 3; }; auto count_diff = [&](int x, int y, int z) -> int { set<int> values; if (x) values.insert(x); if (y) values.insert(y); if (z) values.insert(z); return (int) values.size(); }; int dp[2][4][4][4][4], val = get_val(S[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); clear_dp(1); 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 = get_val(S[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++) { int to_add1 = count_diff(d, d1, d2); dp[curr][d][d1][d3][d4] = max(dp[curr][d][d1][d3][d4], dp[prev][d1][d2][d3][d4] + to_add1); int to_add2 = count_diff(d, d3, d4); dp[curr][d1][d2][d][d3] = max(dp[curr][d1][d2][d][d3], dp[prev][d1][d2][d3][d4] + to_add2); } } 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; }

Compilation message (stderr)

miners.cpp: In lambda function:
miners.cpp:17:5: warning: control reaches end of non-void function [-Wreturn-type]
   17 |     };
      |     ^
#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...