Submission #110003

#TimeUsernameProblemLanguageResultExecution timeMemory
110003ArturgoCoin Collecting (JOI19_ho_t4)C++14
100 / 100
266 ms4984 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...