Submission #218503

#	Time	Username	Problem	Language	Result	Execution time	Memory
218503		socho	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	555 ms	240200 KiB

boxes

#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
 
const long long MXN = 1000005;
long long n, k, l, pos[MXN], rpos[MXN];
long long dpleft[MXN];
long long dpright[MXN];
 
long long delivery(int N, int K, int L, int p[]) {
	for (int i=0; i<MXN; i++) {
		dpleft[i] = -1;
		dpright[i] = -1;
	}
	n = N;
	k = K;
	l = L;
	for (int i=0; i<n; i++) {
		pos[i] = p[i];
		rpos[i] = L - p[i];
	}
	long long best = LLONG_MAX;
	for (int i=0; i<n; i++) {
		dpleft[i] = pos[i] * 2;
		if (i - k >= 0) dpleft[i] += dpleft[i-k];
	}
	for (int i=n-1; i>=0; i--) {
		dpright[i] = rpos[i] * 2;
		if (i + k < n) dpright[i] += dpright[i+k];
	}
	// for (int i=0; i<n; i++) cout << dpleft[i] << ' '; cout << endl;
	// for (int i=0; i<n; i++) cout << dpright[i] << ' '; cout << endl;
	
	best = min(best, dpleft[n-1]);
	best = min(best, dpright[0]);
	
	for (int i=0; i<n-1; i++) {
		best = min(best, dpleft[i] + dpright[i+1]);
	}
	for (int i=0; i<n-1; i++) {
		// skip i..i+k-1 using the circle
		long long unt = l;
		if (i >= 1) unt += dpleft[i-1];
		if (i + k < n) unt += dpright[i+k];
		best = min(best, unt);
	}
	
	return best;
	
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:27:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  for (int i=n-1; i>=0; i--) {
             ~^~

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