Submission #106985

#	Time	Username	Problem	Language	Result	Execution time	Memory
106985		hugo_pm	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	3 ms	384 KiB

boxes

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

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int nbTeams, maxCarry, nbPos;
const int borne = (int)(1e7) + 5;
ll dp[borne][2];
int hd[borne][2];
int pos[borne];

void comp(int gt)
{
	dp[0][gt] = 0;
	form2(deliv, 1, nbTeams+1) {
		ll rep = dp[deliv-1][gt];
		if (deliv > 1 && (deliv-1) % maxCarry == 0) rep += 2*hd[deliv-2][gt];
		rep += hd[deliv-1][gt];
		if (deliv > 1) rep -= hd[deliv-2][gt];

		dp[deliv][gt] = rep;
	}
	form2(deliv, 1, nbTeams+1) dp[deliv][gt] += hd[deliv-1][gt];
}

long long delivery(int N, int K, int L, int p[])
{
	nbTeams = N;
	maxCarry = K;
	nbPos = L;

	form(i, nbTeams) pos[i] = p[i];

	hd[0][0] = pos[0];
	form2(i, 1, nbTeams) {
		hd[i][0] = hd[i-1][0] + (pos[i] - pos[i-1]);
	}

	hd[0][1] = nbPos - pos[N-1];
	form2(i, 1, nbTeams) {
		int nextPos = N-i-1;
		int prevPos = N-i;
		hd[i][1] = hd[i-1][1] + (pos[prevPos] - pos[nextPos]);
	}

	comp(0); comp(1);
	ll rep = BIG;

	form(g, nbTeams+1) {
		int rst = nbTeams-g;
		chmin(rep, dp[g][0] + dp[rst][1]);
	}

	return rep;
}

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