Submission #596603

#	Time	Username	Problem	Language	Result	Execution time	Memory
596603		PiejanVDC	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	520 ms	267180 KiB

boxes

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

long long delivery(int n, int k, int L, int positions[]) {

    vector<long long>l(n+1),r(n+1);

    l[0] = r[0] = 0;

    for(int i = 1 ; i <= n ; i++) {
        int p = max(0, i - k);
        l[i] = l[p] + (long long)2*(positions[i-1]);
        r[i] = r[p] + (long long)2*(L - positions[n - i]);
        //cout << l[i] << ' ' << r[i] << '\n';
    }

    long long ans = (long long)1e18;

    for(int i = 0 ; i <= n ; i++) {
        ans = min(ans, l[i] + r[n-i]);
        if(n-i-k >= 0) ans = min(ans, l[i] + r[max(0, n - i - k)] + L);
        //cout << i << ' ' << ans << '\n';
    }

    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