Submission #1127717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127717		mariza	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	431 ms	196236 KiB

boxes

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

typedef long long ll;
const ll INF=1e18;

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

    ll pref[n];
    for(ll i=0; i<k; i++){
        pref[i]=p[i]+min((ll)p[i],l-p[i]);
    }
    for(ll i=k; i<n; i++){
        pref[i]=pref[i-k]+p[i]+min((ll)p[i],l-p[i]);
    }

    ll suf[n];
    for(ll i=n-1; i>=n-k; i--){
        suf[i]=l-p[i]+min((ll)p[i],l-p[i]);
    }
    for(ll i=n-k-1; i>=0; i--){
        suf[i]=suf[i+k]+l-p[i]+min((ll)p[i],l-p[i]);
    }

    ll ans=min(suf[0],pref[n-1]);
    for(ll i=1; i<n; i++){
        ans=min(ans,pref[i-1]+suf[i]);
    }
    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