# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970813 |
2024-04-27T10:30:55 Z |
Ludissey |
Miners (IOI07_miners) |
C++14 |
|
593 ms |
524288 KB |
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> a;
vector<vector<vector<vector<vector<int>>>>> memo;
int calcExtra(int c, int prev, int prev2){
if(prev==3) return 1;
else if(prev2==3){
if(prev!=c) return 2;
else return 1;
}
if(c!=prev&&prev2!=c&&prev2!=prev) return 3;
else if(c==prev&&prev2==c) return 1;
else return 2;
}
int dp(int x, int prev, int prevprev, int prev2, int prevprev2){
if(x==sz(a)) return 0;
if(memo[x][prev][prevprev][prev2][prevprev2]!=-1) return memo[x][prev][prevprev][prev2][prevprev2];
int mine1=dp(x+1,a[x], prev ,prev2,prevprev2)+calcExtra(a[x],prev,prevprev);
int mine2=dp(x+1,prev,prevprev, a[x], prev2)+calcExtra(a[x],prev2,prevprev2);
return memo[x][prev][prevprev][prev2][prevprev2]=max(mine1,mine2);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
a.resize(n);
memo.resize(n, vector<vector<vector<vector<int>>>>(4,vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));
for (int i = 0; i < n; i++)
{
char c; cin >>c;
if(c=='M') a[i]=0;
else if(c=='B') a[i]=1;
else if(c=='F') a[i]=2;
}
cout << dp(0,3,3,3,3)<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
27484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
54612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
187 ms |
136284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
593 ms |
407960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
373 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |