Submission #384709

#	Time	Username	Problem	Language	Result	Execution time	Memory
384709		qpwoeirut	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	1 ms	364 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

#define idx first
#define cost second

typedef long long ll;
typedef pair<ll,ll> pll;

const ll INF = 1e18;

ll delivery(int n, int k, int l, int p[]) {
    const ll N = n, K = k, L = l;
    deque<pll> lft, rht;
    lft.emplace_back(0LL, 0LL);
    rht.emplace_back(0LL, 0LL);
    for (int i=1; i<=N; ++i) {
        while (lft.size() > 0 && lft.front().idx + K < i) lft.pop_front();
        while (rht.size() > 0 && rht.front().idx + K < i) rht.pop_front();
        if (p[i-1] <= L/2) {
            assert(lft.size() > 0);

            const ll cur = lft.front().cost + 2LL * p[i-1];
            if (i == N) return cur;

            if (p[i] <= L/2) {
                while (lft.size() > 0 && lft.back().cost >= cur) lft.pop_back();
                lft.emplace_back(i, cur);
            } else {
                while (rht.size() > 0 && rht.back().cost >= cur) rht.pop_back();
                rht.emplace_back(i, cur);
            }
        } else {
            assert(lft.size() + rht.size() > 0);
            const ll from_left = lft.empty() ? INF : lft.front().cost + L;
            const ll from_right = rht.empty() ? INF : rht.front().cost + 2LL * (L - p[rht.front().idx]);

            const ll cur = min(from_left, from_right);
            if (i == N) return cur;

            while (rht.size() > 0 && rht.back().cost >= cur) rht.pop_back();
            rht.emplace_back(i, cur);
        }
    }
    assert(0);
}

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