Submission #928571

#	Time	Username	Problem	Language	Result	Execution time	Memory
928571		OAleksa	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	420 ms	245268 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e7 + 69;
long long dp1[N], dp2[N];
long long delivery(int n, int k, int l, int a[]) {
   for (int i = 1;i <= n;i++)
      dp1[i] = dp1[max(0, i - k)] + min(l, 2 * a[i - 1]);
   for (int i = n;i >= 1;i--)
      dp2[i] = dp2[min(n + 1, i + k)] + min(l, 2 * (l - a[i - 1]));
   long long ans = min(dp1[n], dp2[1]);
   for (int i = 1; i < n;i++)
      ans = min(ans, dp1[i] + dp2[i + 1]);
   return ans;
}
/*
3 2 8
1 2 5
*/

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