Submission #835104

#	Time	Username	Problem	Language	Result	Execution time	Memory
835104		MadokaMagicaFan	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	666 ms	276368 KiB

boxes

#include "bits/stdc++.h"
#include "boxes.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

const int N = 1e7;
ll inf = 1e17;
ll sp[2*N+5];

ll solve(int k, vector<ll> &v) {
	ll ans = 0;
	int p = sz(v) - 1;
	while (p > -1) {
		ans += v[p];
		p -= k;
	}
	return ans*2ll;
}

ll delivery(int n, int k, int L, int p[]) {
	for (int i = 0; i <= 2*k; ++i)
		sp[i] = inf;
	ll ans = inf;
	ll l = L;

	vector<ll> left, right;
	for (int i = 0; i < n; ++i) {
		if (p[i] <= L/2) left.pb(p[i]);
		else right.pb(l - p[i]);
	}

	sort(left.begin(), left.end());
	sort(right.begin(), right.end());

	if (sz(right) == 0) return solve(k, left);
	if (sz(left) == 0 || left.back() == 0) return solve(k, right);

	ll t;
	for (int j = 0; j <= k; ++j) {
		t = 0;
		if (j) t += l;
		else t += 2ll*left.back();
		int p = sz(left)-(k-j)-1;
		while (p >= 0) {
			t += 2ll * left[p];
			p -= k;
		}
		
		sp[j] = min(sp[j], t);
		if (p < -1 && p+k < sz(left)) {
			t -= 2ll*left[p+k];
			t += l;
			sp[j-1-p] = min(sp[j-1-p], t);
		}
	}

	for (int j = 0; j <= 2*k; ++j) {
		t = sp[j];
		int p = sz(right)-j-1;
		while (p >= 0) {
			t += 2ll * right[p];
			p -= k;
		}
		ans = min(ans, t);
	}

	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:45:7: warning: declaration of 'int p' shadows a parameter [-Wshadow]
   45 |   int p = sz(left)-(k-j)-1;
      |       ^
boxes.cpp:22:38: note: shadowed declaration is here
   22 | ll delivery(int n, int k, int L, int p[]) {
      |                                  ~~~~^~~
boxes.cpp:61:7: warning: declaration of 'int p' shadows a parameter [-Wshadow]
   61 |   int p = sz(right)-j-1;
      |       ^
boxes.cpp:22:38: note: shadowed declaration is here
   22 | ll delivery(int n, int k, int L, int p[]) {
      |                                  ~~~~^~~

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