Submission #1098878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098878		alexander_707070	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2036 ms	15952 KiB

boxes

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

#define MAXN 1000007
using namespace std;

const long long inf=1e17;

int n,k,L;
int team[2*MAXN];
long long dp[2*MAXN];

int cost(int l,int r){
    int a=min(team[l],L-team[r]);
    int c=team[r]-team[l];

    return min(2*(a+c),L);
}

long long delivery(int N, int K, int LL,int p[]) {
    n=N; k=K; L=LL;

    for(int i=1;i<=n;i++){
        team[i]=p[i-1];
    }

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

    for(int i=1;i<=n;i++){
        dp[i]=inf;
        for(int f=max(i-k+1,1);f<=i;f++){
            dp[i]=min(dp[i],dp[f-1]+cost(f,i));

            if(team[i]<L/2)break;
        }
    }

    if(n<=k)dp[n]=min(dp[n],L+0LL);

    return dp[n];
}

/*int main(){

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

	return 0;
}*/

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