Submission #786679

#	Time	Username	Problem	Language	Result	Execution time	Memory
786679		vnm06	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	340 KiB

boxes

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

int sL[10000005], brL=0, tL=0;
int sR[10000005], brR=0, tR=0;
long long dpL[10000005];
long long dpR[10000005];

long long delivery(int N, int K, int L, int p[])
{
    for(int i=0; i<N; i++)
    {
        if(p[i]==0) continue;
        if(p[i]<=L/2) sL[brL]=p[i], brL++;
        else sR[brR]=p[i], brR++;
    }
    sort(sL, sL+brL);
    sort(sR, sR+brR);
    reverse(sR, sR+brR);
    for(int i=0; i<brL; i++)
    {
        dpL[i]=2*sL[i];
        if(i>=K) dpL[i]+=dpL[i-K];
    }
    for(int i=0; i<brR; i++)
    {
        dpR[i]=2*(L-sR[i]);
        if(i>=K) dpR[i]+=dpR[i-K];
    }
    long long mans=2*L;
    if(brL+brR<=K) mans=L;
    if(brL==0 && brR==0) return 0;
    if(brL==0) return dpR[brR-1];
    if(brR==0) return dpL[brL-1];
    mans=min(mans, dpL[brL-1]+dpR[brR-1]);
    for(int i=1; i<=K-1; i++)
    {
        long long ch=L;
        if(brL>i) ch+=dpL[brL-1-i];
        if(brR>K-i) ch+=dpR[brR-1-K+i];
        mans=min(mans, ch);
    }
    return mans;
}

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