Submission #138733

#	Time	Username	Problem	Language	Result	Execution time	Memory
138733		Talant	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	658 ms	248108 KiB

boxes

#include "boxes.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int NN = (1e7 + 5);
const long long inf = (1e18 + 7);

int n,k,l;
int a[NN];
long long dp[NN];
long long d[NN];
long long ans = inf;

long long delivery(int N, int K, int L, int p[]) {
      n = N,k = K,l = L;

      for (int i = 1; i <= n; i ++) {
            a[i] = p[i - 1];
            dp[i] = inf;
            d[i] = inf;
      }
      d[n + 1] = 0;
      dp[0] = 0;

      for (int i = 1; i <= n; i ++) {
            dp[i] = min(dp[i],dp[i - k >= 0 ? i - k : 0] + min(a[i] * 2,l));
      }
      for (int i = n; i >= 1; i --) {
            d[i] = min(d[i],d[i + k <= n ? i + k : n + 1] + min((L - a[i]) * 2,l));
      }

      for (int i = 0; i < n + 1; i ++) {
            ans = min(ans,dp[i] + d[i + 1]);
      }
      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