Submission #70564

#	Time	Username	Problem	Language	Result	Execution time	Memory
70564		Navick	선물상자 (IOI15_boxes)	C++17	100 / 100	500 ms	196148 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 1e7 + 10;

ll dp[maxN], pd[maxN];

long long delivery(int n, int k, int L, int p[]) {
   	
	
	for (int i=1; i<=n; i++)
	{
		int j = max(0, i - k);
		dp[i] = dp[j] + min((ll)L, 2LL * p[i - 1]);
	}
	
	for (int i=n-1; i>=0; i--)
	{
		int j = min(n, i + k);
		pd[i] = pd[j] + min((ll)L, 2LL*(L - p[i]));
	}

	ll ans = (ll)n * L;

	for (int i=0; i<=n; i++) 
		ans = min(ans, dp[i] + pd[i]);

	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