# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
535167 |
2022-03-09T14:31:56 Z |
kebine |
Miners (IOI07_miners) |
C++17 |
|
161 ms |
592 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#pragma GCC optimize("Ofast")
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
int n;
string s;
cin >> n >> s;
int dp[2][4][4][4][4];
memset(dp, -1, sizeof(dp));
dp[0][0][0][0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= 3; j++){
for(int k = 0; k <= 3; k++){
for(int l = 0; l <= 3; l++){
for(int m = 0; m <= 3; m++){
if(dp[i % 2][j][k][l][m] == -1) continue;
int nxt, cur = 1;
if(s[i] == 'M') nxt = 1;
else if(s[i] == 'B') nxt = 2;
else nxt = 3;
if(j > 0 and j != nxt) cur++;
if(k > 0 and k != nxt and k != j) cur++;
dp[(i + 1) % 2][nxt][j][l][m] = max(dp[(i+1)%2][nxt][j][l][m], dp[i%2][j][k][l][m] + cur);
cur = 1;
if(l > 0 and l != nxt) cur++;
if(m > 0 and m != l and m != nxt) cur++;
dp[(i + 1) % 2][j][k][nxt][l] = max(dp[(i+1)%2][j][k][nxt][l], dp[i%2][j][k][l][m] + cur);
}
}
}
}
}
int ans = 0;
for(int i = 0; i < 2; i++){
for(int j = 0; j <= 3; j++){
for(int k = 0; k <= 3; k++){
for(int l = 0; l <= 3; l++){
for(int m = 0; m <= 3; m++){
ans = max(ans, dp[i][j][k][l][m]);
}
}
}
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
592 KB |
Output is correct |