Submission #1044912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044912		vanea	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	436 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
using ll = long long;
using ld = long double;

const ll INF = 1e18;

ll delivery(int n, int k, int l, int p[]) {
    vector<ll> arr1(n+1), arr2(n+2);
    int rem = k;
    ll ans = INF;
    for(int i = 1; i <= n; i++) {
        ll curr = arr1[i-1];
        int last = (i >= 2 ? p[i-2] : 0);
        if(rem == 0) {
            ll mn = min(2 * last + (p[i-1] - last),
                        (l - last + (l - p[i-1])));
            curr += mn;
            rem = k;
        }
        else curr += p[i-1]-last;
        arr1[i] = curr;
        --rem;
    }
    rem = k;
    for(int i = n; i >= 1; i--) {
        ll curr = arr2[i+1];
        int last = (i != n ? p[i] : l);
        if(rem == 0) {
            ll mn = min(p[i] + p[i-1], 2*(l-p[i]) + (last - p[i-1]));
            curr += mn;
            rem = k;
        }
        else curr += last-p[i-1];
        arr2[i] = curr;
        --rem;
    }
    for(int i = 0; i <= n; i++) {
        int add1 = 0, add2 = 0;
        if(i) add1 = min(p[i-1], l-p[i-1]);
        if(i != n) add2 = min(p[i], l-p[i]);
        ans = min(ans, add1+add2+arr1[i]+arr2[i+1]);
    }
    return ans;
}
/*
int main()
{
    int arr[3] = {1, 2, 5};
    cout << delivery(3, 2, 8, arr);
}*/

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