Submission #600401

#	Time	Username	Problem	Language	Result	Execution time	Memory
600401		Bench0310	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	1480 ms	293980 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"

using namespace std;
typedef long long ll;

const int N=10000000;
ll one[N];
ll two[N];

ll delivery(int n,int k,int l,int p[])
{
    for(int i=0;i<n;i++) if(p[i]==0) p[i]=l;
    sort(p,p+n);
    while(n>=1&&p[n-1]==l) n--;
    if(n==0) return 0;
    for(int i=0;i<n;i++) one[i]=(i>=k?one[i-k]:0)+2*p[i];
    for(int i=n-1;i>=0;i--) two[i]=(i+k<n?two[i+k]:0)+2*(l-p[i]);
    ll res=min(one[n-1],two[0]);
    for(int i=0;i+1<n;i++) res=min(res,one[i]+two[i+1]);
    if(n<=k) res=min(res,ll(l));
    for(int i=0;i+k-1<n;i++) res=min(res,l+(i-1>=0?one[i-1]:0)+(i+k<n?two[i+k]:0));
    return res;
}

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