Submission #134020

#	Time	Username	Problem	Language	Result	Execution time	Memory
134020		dragonslayerit	Miners (IOI07_miners)	C++14	100 / 100	182 ms	100656 KiB

miners

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8