Submission #163154

#	Time	Username	Problem	Language	Result	Execution time	Memory
163154		kostia244	Boxes with souvenirs (IOI15_boxes)	C++14	35 / 100	1320 ms	400 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
ll n, k, l;
vi pos, dpl, dpr;
ll solve() {
	ll ans = LLONG_MAX;
	dpl.assign(n + 2,0);
	dpr.assign(n + 2,0);
	ll p, cst;
	p = cst = 0;
	for (int i = 1; i <= n; i++) {
		cst += min(abs(p - pos[i]), l - abs(p - pos[i])), p = pos[i];
		dpl[i] = cst + min(p, l - p);
		if (i % k == 0) {
			cst += min(p, l - p);
			p = 0;
		}
	}
	ans = dpl[n], p = 0, cst = 0;
	for (int i = n; i; i--) {
		cst += min(abs(p - pos[i]), l - abs(p - pos[i])), p = pos[i];
		dpr[i] = cst + min(p, l - p);
		if ((n - i + 1) % k == 0) {
			cst += min(p, l - p);
			p = 0;
		}
		ans = min(ans, dpr[i] + dpl[i - 1]);
	}
	return ans;
}
long long delivery(int N, int K, int L, int P[]) {
	n = N, k = K, l = L;
	pos.resize(n + 2);
	for (int i = 0; i < n; i++)
		pos[i + 1] = P[i];
	ll ans = solve();
	if(N<11)
	do {
		ans = min(ans, solve());
	} while(next_permutation(pos.begin()+1, pos.begin()+1+n));
	return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'll solve()':
boxes.cpp:25:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  for (int i = n; i; i--) {
               ^

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