제출 #254172

#제출 시각아이디문제언어결과실행 시간메모리
254172tdmiMiners (IOI07_miners)C++14
92 / 100
395 ms204664 KiB
#include <bits/stdc++.h> using namespace std; const int MAXSHIPS = 100*1000; const int MINUSINF = -(MAXSHIPS * 3 + 1); int nbship; int ships[MAXSHIPS]; int maxcoal[MAXSHIPS][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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...