# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
197547 |
2020-01-21T16:02:09 Z |
SamAnd |
Miners (IOI07_miners) |
C++17 |
|
159 ms |
632 KB |
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=100005;
const int INF=1000000000;
int n;
char a[N];
int dp[4][4][4][4];
int ydp[4][4][4][4];
int main()
{
//freopen("input.txt","r",stdin);
cin>>n;
cin>>a;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=-INF;
dp[3][3][3][3]=0;
for(int i=1;i<=n;++i)
{
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ydp[x1][y1][x2][y2]=-INF;
int z;
if(a[i-1]=='M')
z=0;
else if(a[i-1]=='B')
z=1;
else
z=2;
for(int x1=0;x1<4;++x1)
{
for(int y1=0;y1<4;++y1)
{
for(int x2=0;x2<4;++x2)
{
for(int y2=0;y2<4;++y2)
{
int b[4]={};
b[x1]=1;
b[y1]=1;
b[z]=1;
ydp[y1][z][x2][y2]=max(ydp[y1][z][x2][y2],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
b[0]=0;
b[1]=0;
b[2]=0;
b[x2]=1;
b[y2]=1;
b[z]=1;
ydp[x1][y1][y2][z]=max(ydp[x1][y1][y2][z],dp[x1][y1][x2][y2]+b[0]+b[1]+b[2]);
}
}
}
}
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
dp[x1][y1][x2][y2]=ydp[x1][y1][x2][y2];
}
int ans=-INF;
for(int x1=0;x1<4;++x1)
for(int y1=0;y1<4;++y1)
for(int x2=0;x2<4;++x2)
for(int y2=0;y2<4;++y2)
ans=max(ans,dp[x1][y1][x2][y2]);
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
632 KB |
Output is correct |