Submission #71781

#	Time	Username	Problem	Language	Result	Execution time	Memory
71781		zubec	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	530 ms	235208 KiB

boxes

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

const int N = 10000010;

int n, k, l, a[N];
long long dp1[N], dp2[N];
long long delivery(int N, int K, int L, int p[]) {
    ll ans = 1e15;
    n = N;
    k = K;
    l = L;
    for (int i = 1; i <= n; i++)
        a[i] = p[i-1];
    for (int i = 1; i <= n; i++){
        int pre = max(0, i-k);
        dp1[i] = dp1[pre] + min((ll)l, a[i]*1LL*2);
    }
    for (int i = n; i >= 1; i--){
        int nxt = min(n+1, i+k);
        dp2[i] = dp2[nxt] + min((ll)l, (l-a[i])*1LL*2);
    }
    for (int i = 0; i <= n; i++){
        ans = min(ans, dp1[i]+dp2[i+1]);
    }

    return ans;

}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:10:48: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 long long delivery(int N, int K, int L, int p[]) {
                                                ^
boxes.cpp:6:11: note: shadowed declaration is here
 const int N = 10000010;
           ^

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