# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55781 | 2018-07-09T03:13:18 Z | okaybody10 | Miners (IOI07_miners) | C++ | 120 ms | 1564 KB |
#include <bits/stdc++.h> using namespace std; const int mn=-1e9; int dp[2][4][4][4][4],cost[4][4][4]; // cost[i][j][k] = 음식이 i,j,k 순으로 들어왔을 경우 광부들로부터 얻을 수 있는 석탄의 량 int change[100007],n; char s[100008]; int main() { scanf("%d %s",&n,s); for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { for(int k=0;k<3;k++) { if(i==3) // 비어있는 경우 : 3, M : 0, B : 1, F : 2 { if(j==3) cost[i][j][k]=1; // 두 개다 비어있으므로 k의 종류에 상관없이 무조건 1 else cost[i][j][k]=1+(j!=k ? 1 : 0); // 한 개는 비어있지 않으므로 j랑 k가 동일한 종류라면 1, 그 외엔 2 } else if(j==3) { cost[i][j][k]=mn; } else { if(i!=j && j!=k && i!=k) cost[i][j][k]=3; else if(i==j && j==k) cost[i][j][k]=1; else cost[i][j][k]=2; } } } } for(int i=0;i<n;i++) { if(s[i]=='M') change[i]=0; else if(s[i]=='B') change[i]=1; else change[i]=2; } 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++) dp[0][i][j][k][l]=mn; dp[0][3][3][3][3]=0; for(int i=0;i<n;i++) { for(int j=0;j<4;j++) for(int k=0;k<4;k++) for(int l=0;l<4;l++) for(int v=0;v<4;v++) dp[(i+1)%2][j][k][l][v]=mn; for(int j=0;j<4;j++) for(int k=0;k<4;k++) for(int l=0;l<4;l++) for(int v=0;v<4;v++) { if(dp[i%2][j][k][l][v]>=0) { dp[(i+1)%2][j][k][v][change[i]]=max(dp[(i+1)%2][j][k][v][change[i]],dp[i%2][j][k][l][v]+cost[l][v][change[i]]); dp[(i+1)%2][k][change[i]][l][v]=max(dp[(i+1)%2][k][change[i]][l][v],dp[i%2][j][k][l][v]+cost[j][k][change[i]]); } } } int ans=mn; 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++) ans=max(ans,dp[n%2][i][j][k][l]); return !printf("%d",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 1352 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 120 ms | 1564 KB | Output is correct |