oj.uz

Submission #74726

# Submission time Handle Problem Language Result Execution time Memory
74726 2018-09-07T03:09:28 Z goodbaton Miners (IOI07_miners) C++14
100 / 100
 180 ms 1000 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 540 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 544 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 552 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 708 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 884 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1000 KB Output is correct