Submission #237886

#	Time	Username	Problem	Language	Result	Execution time	Memory
237886		rama_pang	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	558 ms	196404 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

long long delivery(int N, int K, int L, int p[]) {
  vector<long long> dpL(N);
  vector<long long> dpR(N);
  for (int i = 0; i < N; i++) {
    dpL[i] = min(p[i], L - p[i]) + p[i] + (i - K < 0 ? 0 : dpL[i - K]);
  }
  for (int i = N - 1; i >= 0; i--) {
    dpR[i] = min(p[i], L - p[i]) + (L - p[i]) + (i + K >= N ? 0 : dpR[i + K]);
  }

  long long ans = min(dpL[N - 1], dpR[0]);
  for (int i = 0; i + 1 < N; i++) {
    ans = min(ans, dpL[i] + dpR[i + 1]);
  }
  for (int i = -1; i + K + 1 <= N; i++) {
    long long cost = (i < 0 ? 0 : dpL[i]) + L + (i + K + 1 >= N ? 0 : dpR[i + K + 1]);
    ans = min(ans, cost);
  }

  return ans;
}

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