# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134020 | 2019-07-21T23:30:39 Z | dragonslayerit | Miners (IOI07_miners) | C++14 | 182 ms | 100656 KB |
#include <cstdio> #include <algorithm> const int INF=1e9+7; int dp[100001][16][16]; int coal[16][4]; char str[100005]; const char mfb[]=" MFB"; void setmax(int& x,int y){ x=std::max(x,y); } int main(){ for(int s=0;s<4;s++){ for(int t=0;t<4;t++){ for(int u=0;u<4;u++){ coal[s*4+t][u]= (s==1||t==1||u==1)+ (s==2||t==2||u==2)+ (s==3||t==3||u==3); } } } int N; scanf("%d",&N); scanf("%s",str); for(int i=0;i<=N;i++){ for(int s=0;s<16;s++){ for(int t=0;t<16;t++){ dp[i][s][t]=-INF; } } } dp[0][0][0]=0; for(int i=0;i<N;i++){ int type=std::find(mfb,mfb+4,str[i])-mfb; for(int s=0;s<16;s++){ for(int t=0;t<16;t++){ setmax(dp[i+1][s/4+type*4][t],dp[i][s][t]+coal[s][type]); setmax(dp[i+1][s][t/4+type*4],dp[i][s][t]+coal[t][type]); } } } /* for(int i=0;i<=N;i++){ for(int s=0;s<16;s++){ for(int t=0;t<16;t++){ printf("dp[%d][%d][%d]=%d\n",i,s,t,dp[i][s][t]); } } } */ int ans=0; for(int s=0;s<16;s++){ for(int t=0;t<16;t++){ ans=std::max(ans,dp[N][s][t]); } } printf("%d\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 5368 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 10424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 25448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 155 ms | 75724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 182 ms | 100656 KB | Output is correct |