Submission #109997

#	Time	Username	Problem	Language	Result	Execution time	Memory
109997		Arturgo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	197 ms	96120 KiB

joi2019_ho_t3

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
using namespace std;

int INFINI = 32000;
int nbPots;
string couleurs;

int ids[256];
vector<int> positions[3];
int nbAvant[3][401];
short dyn[401][401][401][3];

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbPots;
  cin >> couleurs;

  ids['R'] = 0;
  ids['G'] = 1;
  ids['Y'] = 2;

  for(int iPot = 0;iPot < nbPots;iPot++) {
    positions[ids[(int)couleurs[iPot]]].push_back(iPot);

    for(int iCouleur = 0;iCouleur < 3;iCouleur++) {
      nbAvant[iCouleur][iPot + 1] = nbAvant[iCouleur][iPot];
    }
    nbAvant[ids[(int)couleurs[iPot]]][iPot + 1]++;
  }

  for(int iR = 0;iR <= (int)positions[0].size();iR++) {
    for(int iG = 0;iG <= (int)positions[1].size();iG++) {
      for(int iY = 0;iY <= (int)positions[2].size();iY++) {
        for(int derCouleur = 0;derCouleur < 3;derCouleur++) {
	  dyn[iR][iG][iY][derCouleur] = INFINI;
	}
      }
    }
  }

  for(int derCouleur = 0;derCouleur < 3;derCouleur++) {
    dyn[0][0][0][derCouleur] = 0;
  }
  
  for(int iR = 0;iR <= (int)positions[0].size();iR++) {
    for(int iG = 0;iG <= (int)positions[1].size();iG++) {
      for(int iY = 0;iY <= (int)positions[2].size();iY++) {
	array<int, 3> curCouleur = {iR, iG, iY};

	for(int derCouleur = 0;derCouleur < 3;derCouleur++) {
	  for(int suivCouleur = 0;suivCouleur < 3;suivCouleur++) {
	    if(suivCouleur != derCouleur && curCouleur[suivCouleur] != (int)positions[suivCouleur].size()) {
	      array<int, 3> suiv = curCouleur;
	      suiv[suivCouleur]++;

	      int pos = positions[suivCouleur][curCouleur[suivCouleur]];

	      int nbDeps = max(0, nbAvant[0][pos] - curCouleur[0])
		+ max(0, nbAvant[1][pos] - curCouleur[1])
		+ max(0, nbAvant[2][pos] - curCouleur[2]);

	      dyn[suiv[0]][suiv[1]][suiv[2]][suivCouleur] = min<int>(
		dyn[suiv[0]][suiv[1]][suiv[2]][suivCouleur],
		dyn[iR][iG][iY][derCouleur] + nbDeps
	      );
	    }
	  }
	}
      }
    }
  }

  int mini = INFINI;
  for(int derCouleur = 0;derCouleur < 3;derCouleur++) {
    mini = min<int>(mini, dyn[positions[0].size()][positions[1].size()][positions[2].size()][derCouleur]);
  }

  if(mini == INFINI)
    cout << -1 << endl;
  else
    cout << mini << endl;
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25