oj.uz

Submission #253684

# Submission time Handle Problem Language Result Execution time Memory
253684 2020-07-28T14:05:01 Z fvogel499 Miners (IOI07_miners) C++14
100 / 100
 820 ms 116796 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int encode(int prevA, int prevB, int prevprevA, int prevprevB, int i, int n) { // on pourrait encore plus optimiser
  // encode pour que les valeurs avec 0 comme prevA ou prevB n'apparaissent pas
  return (i*256)+((prevA*64)+(16*prevB)+(4*prevprevA)+(prevprevB));
}

vector<int> decode(int encoded) {
  int i = encoded/256;
  encoded -= i*256;
  int a = encoded/64;
  encoded -= a*64;
  int b = encoded/16;
  encoded -= b*16;
  int c = encoded/4;
  encoded -= c*4;
  vector<int> v = {a, b, c, encoded};
  return v;
}

int score(int a, int b, int c) {
  vector<int> u = {a, b, c};
  sort(u.begin(), u.end());
  if (u[0] == 0 and u[1] == 0) {
    return 1;
  }
  else if (u[0] == 0 and u[1] != 0) {
    if (u[1] != u[2]) {
      return 2;
    }
    else {
      return 1;
    }
  }
  else {
    if (u[1] == u[2] and u[2] == u[0]) { // all equal
      return 1;
    }
    if (u[0] != u[1] and u[1] != u[2] and u[0] != u[2]) { // all different
      return 3;
    }
    else {
      return 2;
    }
  }
}

int miners(int situations [], int data [], int n, int i, int encoded) {
  if (i == n) {
    return 0;
  }

  if (situations[encoded] == -1) {
    vector<int> decoded = decode(encoded);
    int prevA = decoded[0];
    int prevB = decoded[1];
    int prevprevA = decoded[2];
    int prevprevB = decoded[3];

    // add to A
    int solA = miners(situations, data, n, i+1, encode(data[i], prevB, prevA, prevprevB, i, n)) + score(data[i], prevA, prevprevA);

    // add to B
    int solB = miners(situations, data, n, i+1, encode(prevA, data[i], prevprevA, prevB, i, n)) + score(data[i], prevB, prevprevB);

    int sol = solA;
    if (solB > solA) {
      sol = solB;
    }

    situations[encoded] = sol;
  }

  return situations[encoded];
}

int main() {
  int n;
  cin >> n;
  const int nbSituations = 256*n;
  int situations [nbSituations];
  for (int i = 0; i < nbSituations; i++) {
    situations[i] = -1;
  }
  int data [n]; // input data
  string inp;
  cin >> inp;
  for (int i = 0; i < n; i++) {
    char loc;
    loc = inp[i];
    if (loc == 'B') {
      data[i] = 1;
    }
    else if (loc == 'M') {
      data[i] = 2;
    }
    else {
      data[i] = 3;
    }
  }
  cout << miners(situations, data, n, 0, encode(0, 0, 0, 0, 0, n));
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6144 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 11904 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 29388 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 87672 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 116796 KB Output is correct