# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
540638 | 2022-03-21T09:56:49 Z | Vladth11 | Miners (IOI07_miners) | C++14 | 210 ms | 616 KB |
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <long double, pii> muchie; const ll NMAX = 1000001; const ll VMAX = 1000001; const ll INF = (1LL << 60); const ll MOD = 1000000007; const ll BLOCK = 1000000; const ll nr_of_bits = 16; int dp[2][4][4][4][4]; int f[4]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; string s; cin >> s; for(int a = 0; a < 4; a++) { for(int b = 0; b < 4; b++) { for(int c = 0; c < 4; c++) { for(int d = 0; d < 4; d++) dp[1][a][b][c][d] = -2e9; } } } dp[1][0][0][0][0] = 0; int maxim = 0; for(int i = 0; i < s.size(); i++) { int cod = 0; if(s[i] == 'M') cod = 1; else if(s[i] == 'F') cod = 2; else cod = 3; for(int a = 0; a < 4; a++) { for(int b = 0; b < 4; b++) { for(int c = 0; c < 4; c++) { for(int d = 0; d < 4; d++) dp[i&1][a][b][c][d] = -2e9; } } } for(int pf = 0; pf < 4; pf++) { for(int ps = 0; ps < 4; ps++) { for(int df = 0; df < 4; df++) { for(int ds = 0; ds < 4; ds++) { f[pf]++; f[cod]++; f[ps]++; int addition = 0; for(int j = 0; j < 4; j++) { addition += (j > 0 && f[j] > 0); f[j] = 0; } addition = max(addition, 0); dp[i&1][ps][cod][df][ds] = max(dp[i&1][ps][cod][df][ds], dp[!(i&1)][pf][ps][df][ds] + addition); maxim = max(maxim, dp[i&1][ps][cod][df][ds]); f[df]++; f[cod]++; f[ds]++; addition = 0; for(int j = 0; j < 4; j++) { addition += (j > 0 && f[j] > 0); f[j] = 0; } addition = max(addition, 0); dp[i&1][pf][ps][ds][cod] = max(dp[i&1][pf][ps][ds][cod], dp[!(i&1)][pf][ps][df][ds] + addition); maxim = max(maxim, dp[i&1][pf][ps][ds][cod]); } } } } } cout << maxim; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 316 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 160 ms | 564 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 210 ms | 616 KB | Output is correct |