Submission #27443

#	Time	Username	Problem	Language	Result	Execution time	Memory
27443		zoomswk	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	774 ms	235292 KiB

boxes

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

long long suff[10000005];
long long pre[10000005];
int pp[10000005];

long long delivery(int N, int K, int L, int p[]){
    for(int i=N; i>=1; i--) pp[i] = p[i-1];
    for(int i=1; i<=K; i++) pre[i] = 2*pp[i];
    for(int i=K+1; i<=N; i++) pre[i] = 2*pp[i] + pre[i-K];
    for(int i=1; i<=K; i++) suff[N-i+1] = 2*(L-pp[N-i+1]);
    for(int i=N-K; i>=1; i--) suff[i] = 2*(L-pp[i]) + suff[i+K];
    long long res = 1e18;
    for(int i=0; i<K; i++){
        long long minv = pre[0];
        for(int j=i; j<=N; j+=K){
            minv += L;
            minv = min(minv, pre[j]);
            res = min(res, suff[j+1]+minv);
        }
    }
    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