제출 #604277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604277		cheissmart	선물상자 (IOI15_boxes)	C++14	100 / 100	754 ms	246916 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

ll delivery(int n, int k, int l, int p[]) {
    vi a;
    for(int i = 0; i < n; i++)
        if(p[i]) a.PB(p[i]);
    n = SZ(a);

    vi x, y;
    for(int i = 0; i < n; i++) {
        if(a[i] < l - a[i]) {
            x.PB(a[i]);
        } else if(l - a[i] < a[i]) {
            y.PB(l - a[i]);
        }
    }
    reverse(ALL(y));
    assert(is_sorted(ALL(x))), assert(is_sorted(ALL(y)));
    auto go = [&] (vi tt) {
        V<ll> dp(SZ(tt) + 1);
        for(int i = 0; i < SZ(tt); i++) {
            dp[i + 1] = dp[max(0, i + 1 - k)] + tt[i] * 2;
        }
        return dp;
    };
    V<ll> dx = go(x), dy = go(y);
    ll ans = 1LL * (n + k - 1) / k * l;
    for(int i = 0; i < k; i++) {
        int take_x = i;
        int take_y = (n - i) % k;
        if(take_x >= SZ(dx) || take_y >= SZ(dy)) continue;
        int take = take_x + take_y, other = n - take;
        assert(other % k == 0);
        ll cost = dx[take_x] + dy[take_y] + 1LL * other / k * l;
        V<ll> dif_x, dif_y;
        for(int j = take_x; j + k < SZ(dx); j += k)
            dif_x.PB(dx[j + k] - dx[j]);
        for(int j = take_y; j + k < SZ(dy); j += k)
            dif_y.PB(dy[j + k] - dy[j]);
        assert(is_sorted(ALL(dif_x))), assert(is_sorted(ALL(dif_y)));
        V<ll> aux(SZ(dif_x) + SZ(dif_y));
        merge(ALL(dif_x), ALL(dif_y), aux.begin());
        ans = min(ans, cost);
        for(ll e:aux) {
            cost += e - l;
            ans = min(ans, cost);
        }
    }
    // for(int i = 0; i < SZ(dx); i++)
    //     for(int j = 0; j < SZ(dy); j++) 
    //         ans = min(ans, dx[i] + dy[j] + 1LL * (n - i - j + k - 1) / k * l);
    cerr << ans << endl;
    return ans;
}

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