Submission #786625

#	Time	Username	Problem	Language	Result	Execution time	Memory
786625		vnm06	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	212 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 delivery(int N, int K, int L, int p[])
{
    for(int i=0; i<N; i++)
    {
        if(p[i]==0) continue;
        if(L%2)
        {
            if(p[i]<=L/2) sL[brL]=p[i], brL++;
            else sR[brR]=p[i], brR++;
        }
        else
        {
            if(p[i]<=L/2) sL[brL]=p[i], brL++;
            else sR[brR]=p[i], brR++;
        }
    }
    sort(sL, sL+brL);
    sort(sR, sR+brR);
    N=brL+brR;
    long long ans=0;
    while(brL-tL>=K)
    {
        tL+=K;
        ans+=2*sL[tL-1];
    }
    while(brR-tR>=K)
    {
        tR+=K;
        ans+=2*(L-sR[tR-1]);
    }
    if(tR==brR) return ans+2*sL[brL-1];
    if(tL==brL) return ans+2*(L-sR[brR-1]);
    long long mans=ans+2*L;
    if(brL+brR-tL-tR<=K) mans=ans+L;
    mans=min(mans, ans+2*sL[brL-1]+2*(L-sR[brR-1]));
    if(brL+brR-tL-tR<=K) return mans;

    ///o1
    int idL=brL-1-(K-(brR-tR));
    mans=min(mans, ans+2*sL[idL]+L);

    ///o2
    int idR=brR-1-(K-(brL-tL));
    mans=min(mans, ans+2*(L-sR[idR])+L);
    return mans;
}

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