Submission #1225425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225425		Hamed_Ghaffari	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	297 ms	165872 KiB

boxes

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

using ll = long long;

const int MXN = 1e7+4;

int a[MXN], b[MXN], sza, szb;
ll dpa[MXN], dpb[MXN];

ll delivery(int N, int K, int L, int p[]) {
    if(L==1) return 0;
    int lim = (L+1)/2-1;
    for(int i=0; i<N; i++)
        if(p[i]) {
            if(p[i]<=lim)
                a[sza++] = p[i];
            else
                b[szb++] = p[i];
        }
    for(int i=0; i<sza; i++) {
        dpa[i] = 2*a[i];
        if(i>=K) dpa[i] += dpa[i-K];
    }
    reverse(b, b+szb);
    for(int i=0; i<szb; i++) {
        dpb[i] = 2*(L-b[i]);
        if(i>=K) dpb[i] += dpb[i-K];
    }
    ll ans = (sza ? dpa[sza-1] : 0) + (szb ? dpb[szb-1] : 0);
    for(int i=0, j; i<=sza && i<=K; i++) {
        j = min(K-i, szb);
        ans = min(ans, L 
        + (i==sza ? 0 : dpa[sza-1-i]) 
        + (j==szb ? 0 : dpb[szb-1-j]));
    }
    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