Submission #1098883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098883		alexander_707070	선물상자 (IOI15_boxes)	C++14	70 / 100	389 ms	87832 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[MAXN];
long long pref[MAXN],suff[MAXN],ans;

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];
    }

    pref[0]=0;
    for(int i=1;i<=n;i++){
        pref[i]=pref[max(i-k,0)]+cost(max(i-k+1,1),i);
    }

    suff[n+1]=0;
    for(int i=n;i>=1;i--){
        suff[i]=suff[min(i+k,n+1)]+cost(i,min(i+k-1,n));
    }

    ans=inf;
    for(int i=0;i<=n;i++){
        ans=min(ans,pref[i]+suff[i+1]);
    }

    if(n<=k)ans=min(ans,L+0LL);

    return ans;
}

/*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: 20 / 20
• Subtask 6: 0 / 30