Submission #562985

#	Time	Username	Problem	Language	Result	Execution time	Memory
562985		Drew_	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	854 ms	293296 KiB

boxes

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

#define ll long long

const int MAX = 1e7 + 69;

ll pfx[MAX], sfx[MAX]; //prefix cost, suffix cost
ll delivery(int N, int K, int L, int p[])
{
    sort(p, p + N);
    for (int i = 0; i < N; ++i)
        pfx[i] =  2*p[i] + (i >= K ? pfx[i-K] : 0);
    for (int i = N-1; i >= 0; --i)
        sfx[i] = 2*(L-p[i]) + (i+K < N ? sfx[i+K] : 0);
    for (int i = 0; i < N; ++i)
        pfx[i] = min(pfx[i], (i >= K ? pfx[i-K] : 0) + L);

    ll res = min(pfx[N-1], sfx[0]);
    for (int i = 0; i+1 < N; ++i)
        res = min(res, pfx[i] + sfx[i+1]);

    return res;
}

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