oj.uz

Submission #172590

# Submission time Handle Problem Language Result Execution time Memory
172590 2020-01-02T07:09:00 Z AlexLuchianov Miners (IOI07_miners) C++14
100 / 100
 248 ms 504 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 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 244 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 476 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 5 ms 376 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 488 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 404 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 504 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 504 KB Output is correct