Submission #107044

#	Time	Username	Problem	Language	Result	Execution time	Memory
107044		hugo_pm	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	1254 ms	411636 KiB

boxes

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#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[2][borne];
int hd[2][borne];
int pos[borne];

void comp(int gt, int base)
{
	dp[gt][0] = 0;
	int deliv = base;
	if (deliv == 0) deliv = maxCarry;
	dp[gt][deliv] = hd[gt][deliv-1];
	deliv += maxCarry;

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

		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[0][i] = hd[0][i-1] + (pos[i] - pos[i-1]);
	}

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

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

	form(gt, 2) form2(i, 1, nbTeams+1) dp[gt][i] += min(hd[gt][i-1], nbPos-hd[gt][i-1]);
	ll rep = BIG;

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

	return rep;
}

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