Submission #1227614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227614		LucaIlie	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	1 ms	328 KiB

boxes

#include "boxes.h"
#include <stdio.h>
#include <algorithm>

using namespace std;

const int MAX_N = 2e7;
const long long INF = 1e18;
int n, k, l;
int p[MAX_N + 1];
long long dp1[MAX_N + 1];
long long dp2[MAX_N + 1];

long long delivery(int N, int K, int L, int P[]) {
    n = N;
    k = K;
    l = L;
    for (int i = 1; i <= n; i++)
        p[i] = P[i - 1];
    sort(p, p + n);
    int pos = 0;
    while (pos + 1 <= n && p[pos + 1] <= l / 2)
        pos++;
    for (int i = 1; i <= pos; i++) {
        if (i <= k)
            dp1[i] = 2 * p[i];
        else
            dp1[i] = dp1[i - k] + 2 * p[i];
    }
    for (int i = n; i > pos; i--) {
        if (i >= n - k + 1)
            dp2[i] = 2 * (l - p[i]);
        else
            dp2[i] = dp2[i + k] + 2 * p[i];
    }

    long long best = dp1[pos] + dp2[pos + 1];
    for (int i = pos + 1; i >= 1 && i >= pos - k + 1; i--) {
        long long c1 = dp1[i - 1];
        long long c2 = dp2[i + k];

        best = min(best, c1 + c2 + l); 
    }

    return best;
}

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