Submission #785483

#	Time	Username	Problem	Language	Result	Execution time	Memory
785483		alexander707070	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	3 ms	304 KiB

boxes

#include<bits/stdc++.h>
#define MAXN 10000007
using namespace std;

const long long inf=1e17;

int n,k,a[MAXN],w;
long long l,r,len;
long long dp[MAXN];

long long cost(int from,int to){
    l=a[from]; r=w-a[to];
    len=a[to]-a[from];

    if(l>r)swap(l,r);
    return min(l+len+r,2*l+2*len);
}

long long delivery(int N, int K, int L,int P[]){
    n=N; k=K; w=L;
    for(int i=1;i<=n;i++){
        a[i]=P[i-1];
    }

    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++){
        dp[i]=inf;
        if(a[i]<=w/2-1){
            dp[i]=dp[max(i-k,0)]+cost(max(i-k+1,1),i);
        }else if(a[max(i-k+1,1)]>=w/2+1){
            dp[i]=dp[max(i-k,0)]+cost(max(i-k+1,1),i);
        }else{
            for(int f=1;f<=min(i,k);f++){
                dp[i]=min(dp[i],dp[i-f]+cost(i-f+1,i));
            }
        }
    }

    return dp[n];
}

/*
int main(){
    cout<<delivery(3,2,8,{1,2,5})<<"\n";
}
*/

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