Submission #519612

#	Time	Username	Problem	Language	Result	Execution time	Memory
519612		silverfish	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	2099 ms	275248 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;

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) + min(2LL*(l-p[i]), l);
		st.insert({s[i], i});
		if(i-k >= 0) st.erase(st.find({s[i-k], i-k}));

		ll mn = min(l, 2LL*p[i]);

		auto it = st.begin();
		int pos = (*it)[1];
		mn = min(mn, 2LL*(l-p[pos]));
		dp[i] = dp[pos-1] + mn;
	}

    return dp[n-1];
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:23:20: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |   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