# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
618804 |
2022-08-02T07:34:21 Z |
1ne |
Miners (IOI07_miners) |
C++14 |
|
1240 ms |
524288 KB |
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
string s;cin>>s;
auto getid = [&](char u){
if (u == 'M')return 0;
else if (u == 'B')return 1;
return 2;
};
vector<int>a(2,-1),b(2,-1);
vector<map<vector<int>,map<vector<int>,int>>>dp(n + 1),came(n + 1);
function<int(int,vector<int>,vector<int>)>solve = [&](int u,vector<int>arr,vector<int>brr){
if (u == n)return 0;
if (came[u][arr][brr])return dp[u][arr][brr];
came[u][arr][brr] = true;
int temp = getid(s[u]);
vector<int>crr(2);
crr[0] = arr[1];
crr[1] = temp;
vector<int>drr(2);
drr[0] = brr[1];
drr[1] = temp;
int cnts = 0,cnts2 = 0;
if (arr[0] != -1)cnts++;
if (arr[1] != -1 && arr[1]!=arr[0])cnts++;
if (temp!=arr[0] && temp!=arr[1])cnts++;
if (brr[0] != -1)cnts2++;
if (brr[1] != -1 && brr[1]!=brr[0])cnts2++;
if (temp!=brr[0] && temp!=brr[1])cnts2++;
long long ans = max(solve(u + 1,crr,brr) + cnts , solve(u + 1,arr,drr) + cnts2);
return dp[u][arr][brr] = ans;
};
cout<<solve(0,a,b)<<'\n';
return 0;
}
# |
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 |
340 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 |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
11648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
31252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
722 ms |
123036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1189 ms |
285544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1012 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1240 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |