Submission #1086284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086284		RiverFlow	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	668 ms	300364 KiB

boxes

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

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

int n, k;

long long l, pre[N], suf[N];

long long modk[N];

long long f(int x) {
    return l * ( (x / k) + (x % k != 0) );
}

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) );
    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));
    }

    int mi[2] = {(n - 1) % k, -1};

    modk[ (n - 1) % k ] = f(n - 1) + suf[n - 1];

    auto cmp = [&](int x, int y) {
        return modk[x] > modk[y] ? 1 : 0;
    };
    for(int i = n - 2; i >= 0; --i) {
        int t = (i + 1) % k;
        ans = min(ans, pre[i] - f(i + 1) + modk[t]);
        for(int i = 0; i < 2; ++i) if (mi[i] != t and mi[i] != -1) {
            ans = min(ans, pre[i] - f(i + 1) + modk[mi[i]] + l);
        }
        int x = i % k;
        if (i + k < n) {
            modk[x] = min(modk[x], f(i) + suf[i]);
        } else {
            modk[x] = f(i) + suf[i];
        }
        if (mi[0] == x) continue ;
        if (mi[1] == x) {
            if (cmp(mi[0], x))
                mi[1] = x;
        } else {
            if (cmp(mi[0], x))
                mi[1] = mi[0], mi[0] = x;
            else if (mi[1] == -1 or cmp(mi[1], x))
                mi[1] = x;
        }
    }

    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:17:24: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   17 | 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;
      |           ^
boxes.cpp:51:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   51 |         for(int i = 0; i < 2; ++i) if (mi[i] != t and mi[i] != -1) {
      |                 ^
boxes.cpp:48:13: note: shadowed declaration is here
   48 |     for(int i = n - 2; i >= 0; --i) {
      |             ^

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