# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
648383 |
2022-10-06T09:50:03 Z |
morasha3 |
Miners (IOI07_miners) |
C++17 |
|
205 ms |
210312 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const ll mod=1e9+7;
#define endl '\n'
ll n;
string s;
ll dp[100007][4][4][4][4];
ll fun(ll idx,ll p,ll p1,ll p2,ll p3)
{
if(idx==n)
{
return 0;
}
if(dp[idx][p][p1][p2][p3]!=-1)return dp[idx][p][p1][p2][p3];
ll o=1;
if(s[idx]=='F')o=3;
else if(s[idx]=='B')o=2;
ll ans=1;
if(p!=0&&p!=o)ans++;
if(p1!=0&&p1!=o)ans++;
if(p1!=0&&p1==p&&o!=p)ans--;
ll c1=fun(idx+1,o,p,p2,p3)+ans;
if(idx==2)
{
ll o1=p;
p=0;
p=o1;
}
ans=1;
if(p2!=0&&p2!=o)ans++;
if(p3!=0&&p3!=o)ans++;
if(p2!=0&&p2==p3&&o!=p2)ans--;
ll c2=fun(idx+1,p,p1,o,p2)+ans;
return dp[idx][p][p1][p2][p3]=max(c1,c2);
}
int32_t main()
{
//freopen("jumping.in","r",stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
memset(dp,-1,sizeof dp);
cout<<fun(0,0,0,0,0);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
200652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
200652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
200760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
200632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
200652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
200684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
200800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
201236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
201608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
203124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
208012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
210312 KB |
Output is correct |