Submission #764186

#	Time	Username	Problem	Language	Result	Execution time	Memory
764186		SanguineChameleon	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	2083 ms	158652 KiB

boxes

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

const long long inf = 1e18L + 20;
const int maxN = 1e7 + 20;
int A[maxN];
long long dp[maxN];

long long delivery(int N, int K, int L, int P[]) {
	for (int i = 1; i <= N; i++) {
		A[i] = P[i - 1];
	}
	for (int i = 1; i <= N; i++) {
		dp[i] = inf;
		for (int j = (i > K && i < N ? K : 1); j <= min(i, K); j++) {
			dp[i] =	min(dp[i], dp[i - j] + min(min(A[i] * 2, (L - A[i - j + 1]) * 2), L));
		}
	}
	return dp[N];
}

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