Submission #646821

#	Time	Username	Problem	Language	Result	Execution time	Memory
646821		Alex_tz307	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	435 ms	196044 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
 
using namespace std;
 
const int kN = 1e7;
const int64_t INF = 1e18L;
int64_t l[1 + kN], r[1 + kN + 1]; 

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}
 
long long delivery(int n, int k, int L, int p[]) {
  for (int i = 1; i <= n; ++i) {
    int last = max(0, i - k); 
    l[i] = l[last] + p[i - 1] + min(p[i - 1], L - p[i - 1]);
  }
 
  for (int i = n; i > 0; --i) {
    int nxt = min(n + 1, i + k);
    r[i] = r[nxt] + (L - p[i - 1]) + min(p[i - 1], L - p[i - 1]);
  }
 
  int64_t best = INF;
  for (int i = 0; i <= n; ++i) {
    minSelf(best, l[i] + r[i + 1]);
  }
  return best;
}

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