Submission #110216

#	Time	Username	Problem	Language	Result	Execution time	Memory
110216		Arturgo	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1035 ms	294116 KiB

boxes

#include "boxes.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long delivery(int nbEquipes, int maxPorte, int nbSections, int positions[]) {
  vector<long long> tempsAvant(nbEquipes, 0), tempsApres(nbEquipes, 0);

  sort(positions, positions + nbEquipes);
  
  for(int iEquipe = 0;iEquipe < nbEquipes;iEquipe++) {
    long long allerRetour = min<long long>(nbSections, 2ll * positions[iEquipe]);
    long long ajout = 0;
    if(iEquipe >= maxPorte)
      ajout = tempsAvant[iEquipe - maxPorte];
    tempsAvant[iEquipe] = ajout + allerRetour;
  }

  for(int iEquipe = nbEquipes - 1;iEquipe >= 0;iEquipe--) {
    long long allerRetour = min<long long>(nbSections, 2ll * (nbSections - positions[iEquipe]));
    long long ajout = 0;
    if(iEquipe + maxPorte < nbEquipes)
      ajout = tempsApres[iEquipe + maxPorte];
    tempsApres[iEquipe] = ajout + allerRetour;
  }

  long long minTemps = min(tempsAvant[nbEquipes - 1], tempsApres[0]);
  for(int iEquipe = 0;iEquipe < nbEquipes - 1;iEquipe++) {
    minTemps = min(minTemps, tempsAvant[iEquipe] + tempsApres[iEquipe + 1]);
  }
  return minTemps;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30