# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
648382 |
2022-10-06T09:49:07 Z |
morasha3 |
Miners (IOI07_miners) |
C++17 |
|
1500 ms |
226536 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;
map<pair<ll,pair<pair<ll,ll>,pair<ll,ll>>>,ll>dp;
ll fun(ll idx,ll p,ll p1,ll p2,ll p3)
{
if(idx==n)
{
return 0;
}
if(dp[{idx,{{p,p1},{p2,p3}}}]!=0)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;
ans=1;
if(p2!=0&&p2!=o)ans++;
if(p3!=0&&p3!=o)ans++;
if(p2!=0&&p2==p3&&o!=p2)ans--;
ll c2=0;
if(idx!=0)
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;
cout<<fun(0,0,0,0,0);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 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 |
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 |
22 ms |
3012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
7348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
31424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
525 ms |
70576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1218 ms |
173440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1594 ms |
226536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |