제출 #777862

#제출 시각아이디문제언어결과실행 시간메모리
777862raysh07Miners (IOI07_miners)C++17
84 / 100
1571 ms201056 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e5 + 69; int n; int dp[N][4][4][4][4]; //states of previous 2 int f(int x, int y, int z){ set <int> st; st.insert(x); st.insert(y); st.insert(z); st.erase(0); return st.size(); } void Solve() { cin >> n; string s; cin >> s; for (int i = 0; i < N; i++){ for (int j = 0; j < 4; j++){ for (int k = 0; k < 4; k++){ for (int l = 0; l < 4; l++){ for (int m = 0; m < 4; m++){ dp[i][j][k][l][m] = -INF; if (i + j + k + l + m == 0) dp[i][j][k][l][m] = 0; } } } } } s = "0" + s; for (int i = 1; i <= n; i++){ int x; if (s[i] == 'M') x = 1; else if (s[i] == 'B') x = 2; else x = 3; for (int i1 = 0; i1 < 4; i1++){ for (int i2 = 0; i2 < 4; i2++){ for (int j1 = 0; j1 < 4; j1++){ for (int j2 = 0; j2 < 4; j2++){ int y = dp[i - 1][i1][i2][j1][j2]; dp[i][x][i1][j1][j2] = max(dp[i][x][i1][j1][j2], y + f(x, i1, i2)); dp[i][i1][i2][x][j1] = max(dp[i][i1][i2][x][j1], y + f(x, j1, j2)); } } } } } int ans = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < 4; j++){ for (int k = 0; k < 4; k++){ for (int l = 0; l < 4; l++){ for (int m = 0; m < 4; m++){ ans = max(ans, dp[i][j][k][l][m]); } } } } } cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...