Submission #107035

#	Time	Username	Problem	Language	Result	Execution time	Memory
107035		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, int base)
{
	dp[0][gt] = 0;
	int deliv = base;
	if (deliv == 0) deliv = maxCarry;
	dp[deliv][gt] = hd[deliv-1][gt];
	deliv += maxCarry;

	while (deliv <= nbTeams) {
		int prev = deliv-maxCarry;
		dp[deliv][gt] = dp[prev][gt];
		dp[deliv][gt] += 2*hd[prev-1][gt];
		dp[deliv][gt] += hd[deliv-1][gt];
		dp[deliv][gt] -= hd[prev-1][gt];

		deliv += maxCarry;
	}

}

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]);
	}

	form(base, maxCarry) {
		comp(0, base);
		comp(1, base);
	}

	form(gt, 2) form2(i, 1, nbTeams+1) dp[i][gt] += hd[i-1][gt];
	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