| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1008105 |
2024-06-26T07:40:34 Z |
vjudge1 |
Miners (IOI07_miners) |
C++17 |
|
42 ms |
32436 KB |
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int dp[MAXN][3][3][3][3];
pii other(int i){
if (i == 0) return {1, 2};
if (i == 1) return {0, 2};
if (i == 2) return {0, 1};
return {0, 0};
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
char x;
cin >> x;
if (x == 'M') a[i] = 0;
else if (x == 'F') a[i] = 1;
else if (x == 'B') a[i] = 2;
}
memset(dp, -inf, sizeof(dp));
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
dp[0][i][i][j][j] = 1;
}
}
debug(a);
for (int i = 1; i <= n; i++){
// but in one
for (int j = 0; j < 3; j++){
for (int k = 0; k < 3; k++){
for (int l = 0; l < 3; l++){
if (a[i] != j) {
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][3 - a[i] - j][j][k][l] + 3);
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][a[i]][j][k][l] + 2);
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][j][j][k][l] + 2);
} else {
pii o = other(a[i]);
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][o.F][a[i]][k][l] + 2);
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][o.S][a[i]][k][l] + 2);
ckmax(dp[i][j][a[i]][k][l], dp[i - 1][a[i]][a[i]][k][l] + 1);
}
if (a[i] != l){
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][3 - a[i] - l][l] + 3);
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][a[i]][l] + 2);
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][l][l] + 2);
} else {
pii o = other(a[i]);
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][o.F][l] + 2);
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][o.S][l] + 2);
ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][l][l] + 1);
}
}
}
}
}
int ans = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
for (int l = 0; l < 3; l++)
ckmax(ans, dp[n][i][j][k][l]);
cout << ans - 5 << endl;
}
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
miners.cpp:49:2: note: in expansion of macro 'debug'
49 | debug(a);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
32088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
32092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
32088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
32092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
32092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
32068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
32088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
32088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
32000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
32088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
32436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
32348 KB |
Output is correct |
