# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
655336 |
2022-11-03T21:02:23 Z |
sword060 |
Miners (IOI07_miners) |
C++17 |
|
286 ms |
111668 KB |
#include <bits/stdc++.h>
using namespace std;
int x,dp[100005][16][16];
map<char,int>mp;
string s;
int f(int a,int b){
int l[4],r=0;
l[0]=0;l[1]=0;l[2]=0;l[3]=0;
l[a&3]++;l[a>>2]++;l[b]++;
for(int i=1;i<=3;i++)r+=(l[i]>0);
return r;
}
int rec(int i,int l,int r){
if(i==x)return 0;
if(~dp[i][l][r])return dp[i][l][r];
int c1=f(l,mp[s[i]]),c2=f(r,mp[s[i]]);
return dp[i][l][r]=max(rec(i+1,(l>>2)|(mp[s[i]]<<2),r)+c1,rec(i+1,l,(r>>2)|(mp[s[i]]<<2))+c2);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
memset(dp,-1,sizeof(dp));
mp['M']=1;mp['F']=2;mp['B']=3;
cin>>x>>s;
cout<<rec(0,0,0);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
100468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
100496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
100500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
100452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
100432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
100380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
100544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
101028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
101612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
103280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
108900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
286 ms |
111668 KB |
Output is correct |