Submission #407360

#	Time	Username	Problem	Language	Result	Execution time	Memory
407360		MDario	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	581 ms	249220 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
long long delivery(int n, int K, int L, int p[]){
    vector<pair<ll, ll>> v1, v2;
    ll k=K, l=L;
    ll a[n+2], a1[n+2];
    a[0]=0;
    for(int i=1; i<=n; i++){
        if(i<k)a[i]=2*p[i-1];
        else a[i]=2*p[i-1]+a[i-k];
    }
    a1[n+1]=0;
    for(int i=n; i>0; i--){
        if(i+k>n+1)a1[i]=2*(l-p[i-1]);
        else a1[i]=2*(l-p[i-1])+a1[i+k];
    }
    ll r=a[n];
    for(int i=1; i+k<=n+1; i++){
        r=min(r, a[i-1]+a1[i+k]+l);
    }
    for(int i=0; i<=n; i++){
        r=min(r, a[i]+a1[i+1]);
    }
    return r;
}

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