Submission #787045

#	Time	Username	Problem	Language	Result	Execution time	Memory
787045		GusterGoose27	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	402 ms	123636 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e7+5;
ll pre[MAXN];

ll delivery(int n, int k, int l, int p[]) {
    // ll cur = 0;
    // int res = 0;
    for (int i = 0; i < n && p[i] <= l/2; i++) {
        if (i < k) pre[i] = 2*p[i];
        else pre[i] = 2*p[i]+pre[i-k];
        // pre[i] = cur+2*p[i];
        // if (res == k-1) {
        //     cur += 2*p[i];
        //     res = 0;
        //     continue;
        // }
        // res++;
    }
    // cur = 0;
    // res = 0;
    for (int i = n-1; i >= 0 && p[i] > l/2; i--) {
        if (i+k >= n) pre[i] = 2*(l-p[i]);
        else pre[i] = 2*(l-p[i])+pre[i+k];
        // pre[i] = cur+2*(l-p[i]);
        // if (res == k-1) {
        //     cur += 2*(l-p[i]);
        //     res = 0;
        //     continue;
        // }
        // res++;
    }
    int div;
    for (div = 0; div < n && p[div] <= l/2; div++) {}
    ll ans = (div ? pre[div-1] : 0) + pre[div];
    for (int i = div-k+1; i < div; i++) {
        int lp = max(i, 0);
        int rp = min(n-1, i+k-1);
        ans = min(ans, (lp ? pre[lp-1] : 0)+pre[rp+1]+l);
    }
    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