제출 #253684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253684		fvogel499	Miners (IOI07_miners)	C++14	100 / 100	820 ms	116796 KiB

miners

#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 / 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