oj.uz

Submission #134020

# Submission time Handle Problem Language Result Execution time Memory
134020 2019-07-21T23:30:39 Z dragonslayerit Miners (IOI07_miners) C++14
100 / 100
 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

miners.cpp: In function 'int main()':
miners.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
miners.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",str);
   ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5368 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10424 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25448 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 75724 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 100656 KB Output is correct