Submission #74726

#	Time	Username	Problem	Language	Result	Execution time	Memory
74726		goodbaton	Miners (IOI07_miners)	C++14	100 / 100	180 ms	1000 KiB

miners

#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>

#define SIZE 100010
#define INF 1000000000

using namespace std;

const int B = 13;

int dp[2][B][B];

int main(){
  int n;
  char s[SIZE];

  scanf("%d%s",&n,s);

  for(int j=0;j<B;j++){
    for(int k=0;k<B;k++){
      dp[0][j][k] = -INF;
    }
  }

  dp[0][B-1][B-1] = 0;

  int t1[4] = {}, t2[4] = {};
  int a,b,c,d,e,j2,k2;
    
  for(int i=0;i<n;i++){
    
    for(int j=0;j<B;j++){
      for(int k=0;k<B;k++){
	dp[1-i%2][j][k] = -INF;
      }
    }

    if(s[i]=='M') e=1;
    else if(s[i]=='F') e=2;
    else if(s[i]=='B') e=3;

    t1[e]++;
    t2[e]++;
    
    for(int j=0;j<B;j++){
      if(j == B-1){
	a = 0;
	b = 0;
      }else{
	a = j/3;
	b = j%3 + 1;
      }
      j2 = b*3+(e-1);

      t1[a]++;
      t1[b]++;

      for(int k=0;k<B;k++){
	if(k == B-1){
	  c = 0;
	  d = 0;
	}else{
	  c = k/3;
	  d = k%3 + 1;
	}
	k2 = d*3+(e-1);

	t2[c]++;
	t2[d]++;
	
	dp[1-i%2][j2][k] = max(dp[1-i%2][j2][k],dp[i%2][j][k] + (t1[1]>0) + (t1[2]>0) + (t1[3]>0));

	dp[1-i%2][j][k2] = max(dp[1-i%2][j][k2],dp[i%2][j][k] + (t2[1]>0) + (t2[2]>0) + (t2[3]>0));

	t2[c]--;
	t2[d]--;
      }
      t1[a]--;
      t1[b]--;
    }
    t1[e]--;
    t2[e]--;
  }

  int ans = 0;

  for(int j=0;j<B;j++){
    for(int k=0;k<B;k++){
      ans = max(ans,dp[n%2][j][k]);
    }
  }

  printf("%d\n",ans);

  return 0;
} 

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%s",&n,s);
   ~~~~~^~~~~~~~~~~~~
miners.cpp:30:15: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int a,b,c,d,e,j2,k2;
               ^

• 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