Submission #389046

#	Time	Username	Problem	Language	Result	Execution time	Memory
389046		faresbasbs	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	540 ms	202168 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
long long n,k,l,num,in[10000001],dp1[10000001],dp2[10000001];

long long delivery(int N , int K , int L , int p[]){
    n = N , k = K , l = L;
    num = l/2;
    long long ans = 1000000000000000000 , v1 = 0 , v2 = 0;
    for(long long i = 1 ; i <= n ; i += 1){
        in[i] = p[i-1];
        if(in[i] <= num){
            if(i >= k){
                dp1[i] = dp1[i-k];
            }
            dp1[i] += 2*in[i];
            v1 = dp1[i];
        }
    }
    for(long long i = n ; i >= 1 ; i -= 1){
        if(in[i] <= num){
            break;
        }
        if(i+k <= n){
            dp2[i] = dp2[i+k];
        }
        dp2[i] += 2*(l-in[i]);
        v2 = dp2[i];
    }
    ans = v1+v2;
    if(k >= n){
        ans = min(ans,l);
    }
    for(long long i = 1 ; i+k-1 <= n ; i += 1){
        if(in[i] <= num && in[i+k-1] > num){
            ans = min(ans,dp1[i-1]+l+dp2[i+k]);
        }
    }
    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