Submission #1045192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045192		vanea	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	434 ms	288652 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> dp1(n+1), dp2(n+2);
    for(int i = 1; i <= n; i++) {
        if(i <= k) {
            dp1[i] = p[i-1];
        }
        else {
            dp1[i] = dp1[i-k]+p[i-1]+p[i-k-1];
        }
    }
    for(int i = n; i >= 1; i--) {
        if(i+k > n) {
            dp2[i] = (l-p[i-1]);
        }
        else {
            dp2[i] = dp2[i+k] + (l-p[i-1]) + (l-p[i+k-1]);
        }
    }
    ll ans = INF;
    for(int i = 0; i <= n; i++) {
        ll 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, dp1[i] + add1 + dp2[i+1] + add2);
    }
    return ans;
}

/*
int main()
{
    int arr[5] = {1,5,5,15,19};
    cout << delivery(5, 2, 20, arr);
}*/

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