제출 #550451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550451		elazarkoren	선물상자 (IOI15_boxes)	C++17	70 / 100	583 ms	244400 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;

struct Seg{
    vector<ll> seg;
    int n;
    Seg (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
    }
    void update(int i, int x) {
        seg[i += n] = x;
        for (i >>= 1; i; i >>= 1) seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
    ll query(int l, int r) {
        ll ans = infinity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) chkmin(ans, seg[l++]);
            if (r & 1) chkmin(ans, seg[--r]);
        }
        return ans;
    }
};

int n, k, l;

ll dpl[MAX_N], dpr[MAX_N];

void CalcL(vi &p) {
    deque<int> d = {0};
    for (int i = 1; i <= n; i++) {
        while (d.front() < i - k) d.pop_front();
        dpl[i] = dpl[d.front()];
//        int m = max(0, i - k);
//        for (int j = i - 1; j >= m; j--) {
//            chkmin(dpl[i], dpl[j]);
//        }
        dpl[i] += min<ll>(l, 2 * p[i]);
        while (!d.empty() && dpl[d.back()] > dpl[i]) d.pop_back();
        d.push_back(i);
    }
}

void CalcR(vi &p) {
    deque<int> d = {n + 1};
    for (int i = n; i >= 0; i--) {
        while (d.front() > i + k) d.pop_front();
        dpr[i] = dpr[d.front()];
//        int m = min(n + 1, i + k);
//        for (int j = i + 1; j <= m; j++) {
//            chkmin(dpr[i], dpr[j]);
//        }
        dpr[i] += min<ll>(l, 2 * (l - p[i]));
        while (!d.empty() && dpr[d.back()] > dpr[i]) d.pop_back();
        d.push_back(i);
    }
}

inline ll Solve(int ind) {
    return dpl[ind - 1] + dpr[ind];
}

long long delivery(int N, int K, int L, int P[]) {
    n = N, k = K, l = L;
    vi p(n + 1);
    ll ans = infinity;
    for (int i = 1; i <= n; i++) p[i] = P[i - 1];
    CalcL(p), CalcR(p);
    for (int ind = 1; ind <= n + 1; ind++) {
        chkmin(ans, Solve(ind));
    }
    return ans;
}
//3 2 8
//1 2 5

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