# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
254174 |
2020-07-29T12:50:00 Z |
tdmi |
Miners (IOI07_miners) |
C++14 |
|
252 ms |
101184 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXSHIPS = 100*1000;
const int MINUSINF = -(MAXSHIPS * 3 + 1);
int nbship;
int ships[MAXSHIPS+1];
int maxcoal[MAXSHIPS+1][4][4][4][4];
string shipstring;
int prodwith(int ship1,int ship2,int ship3)
{
if(ship3==3 && ship1==ship2)
{
return 1;
}
else if(ship3==3 && ship2==3)
{
return 1;
}
else if(ship3==3)
{
return 2;
}
if(ship1==ship2 && ship1==ship3)
{
return 1;
}
else if(ship1==ship2 || ship1==ship3 || ship2==ship3)
{
return 2;
}
else
{
return 3;
}
}
signed main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin>>nbship>>shipstring;
for(int iship = 0 ; iship < nbship ; iship++)
{
ships[nbship-iship-1]=(shipstring[iship]=='M'?0:(shipstring[iship]=='B'?1:2));
}
for(int iship = 0 ; iship < nbship+1 ; iship++)
{
for(int i = 0 ; i < 4 ; i++)
{
for(int j = 0 ; j < 4 ; j++)
{
for(int k = 0 ; k < 4 ; k++)
{
for(int l = 0 ; l < 4 ; l++)
{
maxcoal[iship][i][j][k][l]=(i==3 && j==3 && k==3 && l==3 ? 0 : MINUSINF);
}
}
}
}
}
for(int iship = nbship ; iship>0 ; iship--)
{
for(int i = 0 ; i < 4 ; i++)
{
for(int j = 0 ; j < 4 ; j++)
{
for(int k = 0 ; k < 4 ; k++)
{
for(int l = 0 ; l < 4 ; l++)
{
maxcoal[iship-1][ships[iship-1]][i][k][l] = max(maxcoal[iship-1][ships[iship-1]][i][k][l] ,maxcoal[iship][i][j][k][l]+prodwith(ships[iship-1],i,j));
maxcoal[iship-1][i][j][ships[iship-1]][k] = max(maxcoal[iship-1][i][j][ships[iship-1]][k] ,maxcoal[iship][i][j][k][l]+prodwith(ships[iship-1],k,l));
}
}
}
}
}
int maxi = 0;
for(int i = 0 ; i < 4 ; i++)
{
for(int j = 0 ; j < 4 ; j++)
{
for(int k = 0 ; k < 4 ; k++)
{
for(int l = 0 ; l < 4 ; l++)
{
maxi = max(maxi,maxcoal[0][i][j][k][l]);
}
}
}
}
cout<<maxi;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
10368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
25656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
75972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
101184 KB |
Output is correct |