Submission #1086281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086281		RiverFlow	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2004 ms	30416 KiB

boxes

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

const int N = (int)1e7 + 2;

int n, k;

long long l;

long long f(int x) {
    return l * ( (x / k) + (x % k != 0) );
}
long long suf[N], pre[N];

long long delivery(int N, int K, int L, int p[]) {
    n = N, k = K, l = L;
    long long ans = (long long)1e17;
    ans = min(ans, f(n) );
    // co le la tinh cost(i): chi phi de nhung gia tri dau
    for(int i = 0; i < n; ++i) {
        long long c = 2LL * p[i];
        if (i - k >= 0) {
            c += pre[i - k];
        }
        pre[i] = c;
    }
    for(int i = n - 1; i >= 0; --i) {
        long long c = 2LL * (l - p[i]);
        if (i + k < n) {
            c += suf[i + k];
        }
        suf[i] = c;
    }

    for(int i = 0; i < n; ++i) {
        ans = min(ans, pre[i] + f(n - i - 1));
        ans = min(ans, suf[i] + f(i));
    }

    for(int i = 0; i < n; ++i)
    for(int j = n - 1; j > i; --j) {
        ans = min(ans, pre[i] + suf[j] + f(j - i - 1));
    }

    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:16:24: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   16 | long long delivery(int N, int K, int L, int p[]) {
      |                    ~~~~^
boxes.cpp:5:11: note: shadowed declaration is here
    5 | const int N = (int)1e7 + 2;
      |           ^

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