Submission #862075

#	Time	Username	Problem	Language	Result	Execution time	Memory
862075		culver0412	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	735 ms	450412 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;

long long delivery(int N, int K, int L, int p[]) {
    sort(p,p+N);
    long long arr[N],brr[N],crr[N],drr[N];
    int st=0;
    while(p[st]==0){
        st++;
        if(st==N){
            return 0;
        }
    }
    for(int i=st;i<N;i++){
        arr[i]=min(p[i]*2,L);
        crr[i]=arr[i];
        if(i-K>=st){
            crr[i]+=crr[i-K];
        }
    }
    for(int i=N-1;i>=st;i--){
        brr[i]=min((L-p[i])*2,L);
        drr[i]=brr[i];
        if(i+K<=N-1){
            drr[i]+=drr[i+K];
        }
    }
    long long ans=min(drr[st],crr[N-1]);
    //cout << drr[st] << '\n';
    for(int i=st;i<N-1;i++){
        //cout << crr[i]+drr[i+1] << '\n';
        ans=min(ans,crr[i]+drr[i+1]);
    }
    //cout << crr[N-1] << '\n';
    return ans;
}

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