Submission #172590

#	Time	Username	Problem	Language	Result	Execution time	Memory
172590		AlexLuchianov	Miners (IOI07_miners)	C++14	100 / 100	248 ms	504 KiB

miners

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

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const states = 16;
int dp[1 + states][1 + states];
int dp2[1 + states][1 + states];
char v[1 + nmax];

int cost_state(int state, int val){
  int frec[4] = {0};
  frec[(state & 3)]++;
  frec[(state >> 2)]++;
  frec[val]++;
  return (0 < frec[1]) + (0 < frec[2]) + (0 < frec[3]);
}
int transform_state(int state, int val){
  return (val << 2) + (state >> 2);
}

int main()
{
  int n;
  cin >> n;
  for(int i = 0; i < states; i++)
    for(int j = 0; j < states; j++)
      dp[i][j] = dp2[i][j] = -nmax;
  dp[0][0] = 0;
  for(int i = 1; i <= n; i++){
    cin >> v[i];
    int val;
    if(v[i] == 'B')
      val = 1;
    else if(v[i] == 'F')
      val = 2;
    else if(v[i] == 'M')
      val = 3;

    for(int j = 0; j < states; j++)
      for(int h = 0; h < states; h++){
        int target = transform_state(j, val), cost = dp[j][h] + cost_state(j, val);
        if(dp2[target][h] < cost)
          dp2[target][h] = cost;
        target = transform_state(h, val);
        cost = dp[j][h] + cost_state(h, val);
        if(dp2[j][target] < cost)
          dp2[j][target] = cost;
      }

    for(int j = 0; j < states; j++)
      for(int h = 0; h < states; h++) {
        dp[j][h] = dp2[j][h];
        dp2[j][h] = -nmax;
      }
  }
  int result = 0;
  for(int i = 0; i < states; i++)
    for(int j = 0; j < states; j++)
      result = MAX(result, dp[i][j]);
  cout << result;
  return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:38:9: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int val;
         ^~~

• 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