Submission #519614

#	Time	Username	Problem	Language	Result	Execution time	Memory
519614		silverfish	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	2059 ms	213600 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
using ll = long long;
const int N = 10000007;

ll dp[N], s[N];
set<array<ll,2>> st;

inline ll mn(ll a, ll b){
	return (a < b ? a : b);
}

long long delivery(int n, int k, int L, int p[]) {
	ll l = L;
	fill(dp, dp+N, 1e18+10);
//	sort(p, p+n);

	for(int i = 0; i < n; ++i){
		s[i] = (i ? dp[i-1] : 0) + mn(2LL*(l-p[i]), l);
		st.insert({s[i], i});
		if(i-k >= 0) st.erase(st.find({s[i-k], i-k}));

		auto it = st.begin();
		int pos = (*it)[1];

		dp[i] = dp[pos-1]+mn(l, mn(2LL*p[i], 2LL*(l-p[pos])));
	}

    return dp[n-1];
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:25:20: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   25 |   int pos = (*it)[1];
      |                    ^

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