Submission #120340

#	Time	Username	Problem	Language	Result	Execution time	Memory
120340		turbat	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	611 ms	291644 KiB

boxes

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

long long a[10000005], dp[10000005], dp1[10000005], ans = 1e18;
long long delivery(int N, int K, int L, int p[]) {
	for (int i = 0;i < N;i++){
		a[i] = L - p[N - 1 - i];
		if (i < K) {
			dp[i + 1] = p[i] * 2;
			dp1[i + 1] = a[i] * 2;
		}
		else {
			dp[i + 1] = dp[i - K + 1] + p[i] * 2;
			dp1[i + 1] = dp1[i - K + 1] + a[i] * 2;
		}
	}
	for (int i = 0;i <= N;i++){
		ans = min(ans,  dp[i] + dp1[N - i]);
		if (i + K <= N) ans = min(ans, dp[i] + L + dp1[N - i - K]);
	}
    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