Submission #928438

#	Time	Username	Problem	Language	Result	Execution time	Memory
928438		OAleksa	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	348 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

long long delivery(int n, int k, int l, int p[]) {
   vector<int> left, right;
   for (int i = 0;i < n;i++) {
      if (p[i] <= l / 2)
         left.push_back(p[i]);
      else
         right.push_back(p[i]);
   }
   auto Solve = [&](vector<int> fi, vector<int> se) {
      long long r = 0, o = 0;
      for (int i = 0;i < (int)fi.size();i++) {
         if (o == 0) {
            if (i == 0)
               r += fi[i];
            else
               r += fi[i - 1] + fi[i];
            o = k - 1;
         }
         else {
            o -= 1;
            r += fi[i] - fi[i - 1];
         }
         if (i == (int)fi.size() - 1)
            r += fi[i];
      }
      o = 0;
      for (int i = (int)se.size() - 1;i >= 0;i--) {
         if (o == 0) {
            if (i == (int)se.size() - 1)
               r += (l - se[i]);
            else
               r += (l - se[i + 1]) + (l - se[i]);
            o = k - 1;
         }
         else {
            o -= 1;
            r += se[i + 1] - se[i];
         }
         if (i == 0)
            r += (l - se[i]);
      }
      long long r1 = 0;
      o = 0;
      int j = -1;
      for (int i = 0;i < (int)fi.size();i++) {
         if (o == 0) {
            if (i == 0)
               r1 += fi[i];
            else
               r1 += fi[i - 1] + fi[i];
            o = k - 1;
         }
         else {
            o -= 1;
            r1 += fi[i] - fi[i - 1];
         }
         if (i == (int)fi.size() - 1) {
            if (se.size() > 0 && o > 0) {
               for (j = 0;j < (int)se.size();j++) {
                  o -= 1;
                  if (j == 0)
                     r1 += se[j] - fi[i];
                  else
                     r1 += se[j] - se[j - 1];
                  if (o == 0 || j == (int)se.size() - 1) {
                     r1 += (l - se[j]);
                     break;
                  }
               }
            }
            else
               r1 += fi[i];
         }
      }
      o = 0;
      for (int i = (int)se.size() - 1;i > j;i--) {
         if (o == 0) {
            if (i == (int)se.size() - 1)
               r1 += (l - se[i]);
            else
               r1 += (l - se[i + 1]) + (l - se[i]);
            o = k - 1;
         }
         else {
            o -= 1;
            r1 += se[i + 1] - se[i];
         }
         if (i == j + 1)
            r1 += (l - se[i]);
      }
      return min(r, r1);
   };
   long long ans = Solve(left, right);
   for (int i = 0;i < (int)left.size();i++)
      left[i] = l - left[i];
   for (int i = 0;i < (int)right.size();i++)
      right[i] = l - right[i];
   reverse(left.begin(), left.end());
   reverse(right.begin(), right.end());
   return min(ans, Solve(right, left));
}
/*
3 1 8
1 2 5
*/

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