Submission #968539

#	Time	Username	Problem	Language	Result	Execution time	Memory
968539		duckindog	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	467 ms	293956 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "boxes.h"
#endif

const int N = 10'000'000 + 10;
long long f[2][N];
long long delivery(int n, int k, int l, int p[]) {
  for (int i = 1; i <= n; ++i) {
    f[0][i] = f[0][max(0, i - k)] + p[i - 1] + min(p[i - 1], l - p[i - 1]);
  }
  for (int i = n; i >= 1; --i) {
    f[1][i] = f[1][min(n + 1, i + k)] + l - p[i - 1] + min(p[i - 1], l - p[i - 1]);
  }
  
  long long answer = 1'000'000'000'000'000'000;
  for (int i = 0; i <= n; ++i) answer = min(answer, f[0][i] + f[1][i + 1]);
  return answer;
}

#ifdef LOCAL
int n, k, l;
int p[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> l;
  for (int i = 0; i < n; ++i) cin >> p[i];

  cout << delivery(n, k, l, p) << "\n";
}
#endif

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