Submission #1178510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178510		sleepntsheep	Boxes with souvenirs (IOI15_boxes)	C11	100 / 100	341 ms	196160 KiB

boxes

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

long long delivery(int N, int K, int L, int p2[]) {
    int*p=p2;
    while(p-p2<N&&*p==0)++p;
    N-=p-p2;

    if(K>N)K=N;
    static long long z,l[10000000],r[10000000];
    z=1e18;

    for(int i=0;i<N;++i)
        if(i<K)l[i]=p[i]*2;
        else l[i]=l[i-K]+p[i]*2;
    for(int i=N-1;i>=0;--i)
        if(i+K>=N)r[i]=(L-p[i])*2;
        else r[i]=r[i+K]+(L-p[i])*2;

    for(int i=0;i+1<N;++i)if(l[i]+r[i+1]<z)z=l[i]+r[i+1];
    for(int i=K+1;i<N;++i)if(r[i]+l[i-K-1]+L<z)z=r[i]+l[i-K-1]+L;

    if(L+(K<N?r[K]:0)<z)z=L+(K<N?r[K]:0);
    if(K<N&&L+l[N-K-1]<z)z=L+l[N-K-1];
    if(l[N-1]<z)z=l[N-1];
    if(r[0]<z)z=r[0];

    return z;
}

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