Submission #432292

#	Time	Username	Problem	Language	Result	Execution time	Memory
432292		chirathnirodha	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	636 ms	202384 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long ll;

long long delivery(int n, int k, int l, int p[]) {
    ll cw[n],acw[n];
    for(int i=0;i<n;i++){
        cw[i]=(ll)p[i]*2;
        if(i>=k)cw[i]+=cw[i-k];
    }
    for(int i=n-1;i>=0;i--){
        acw[i]=((ll)l-(ll)p[i])*2;
        if(i<n-k)acw[i]+=acw[i+k];
    }
    ll ans=INT64_MAX;
    ans=min(cw[n-1],acw[0]);
    for(int i=0;i<n-1;i++){
        ans=min(ans,cw[i]+acw[i+1]);
    }
    if(n<=k)ans=min(ans,(ll) l);
    else{
        ans=min(ans,acw[k]+(ll)l);
        ans=min(ans,cw[n-1-k]+(ll)l);
        for(int i=0;i<n-k-1;i++){
            ans=min(ans,cw[i]+acw[i+k+1]+(ll)l);
        }
    }
    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