Submission #110003

#	Time	Username	Problem	Language	Result	Execution time	Memory
110003		Arturgo	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	266 ms	4984 KiB

joi2019_ho_t4

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

int nbIci[2][100000];

int main() {
  int nbCols;
  cin >> nbCols;

  long long totalDist = 0;
  for(int iPiece = 0;iPiece < 2 * nbCols;iPiece++) {
    int col, lig;
    cin >> col >> lig;

    int ncol = max(1, min(nbCols, col));
    int nlig = max(1, min(2, lig));
    totalDist += abs(lig - nlig) + abs(col - ncol);
    nbIci[nlig - 1][ncol - 1]++;
  }

  int resteBas = 0, resteHaut = 0;
  for(int iPos = 0;iPos < nbCols;iPos++) {
    resteBas += nbIci[0][iPos] - 1;
    resteHaut += nbIci[1][iPos] - 1;

    if(resteBas > 0 && resteHaut < 0) {
      int transfert = min(resteBas, -resteHaut);
      totalDist += transfert;
      resteBas -= transfert;
      resteHaut += transfert;
    }
    if(resteBas < 0 && resteHaut > 0) {
      int transfert = min(-resteBas, resteHaut);
      totalDist += transfert;
      resteBas += transfert;
      resteHaut -= transfert;
    }

    totalDist += abs(resteBas) + abs(resteHaut);
  }

  cout << totalDist << endl;
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63