Submission #1130123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130123		Art_ogo	Boxes with souvenirs (IOI15_boxes)	C++17	35 / 100	1 ms	328 KiB

boxes

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef ONPC
    #pragma GCC target("avx2")
    #pragma GCC target("popcnt")

    #define cerr if (false) cerr
#endif

#define all(v) v.begin(), v.end()
#define watch(x) cerr << #x << ':' << x << endl;

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

typedef __int128_t int128;

mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
    return uniform_int_distribution<ll>(l, r)(gen64);
}

const int mod = 1e9 + 7;

inline int mult(int a, int b) {
    return (1LL * a * b) % mod;
}

template<class T>
bool umax(T &a, const T &b) {
    return (a < b ? a = b, true : false);
}

const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;

const int maxn = 1e5 + 10, maxm = 20, maxc = 5000 + 10, maxq = 2e5 + 10, logn = 20, msqn = 45, cpr = 500, maxbit = 32;

long long delivery(int N, int K, int L, int P[]) {
  ll n = N, k = K, l = L;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
      a[i] = P[i];

    sort(all(a));
    vector<vector<ll>> pref(k, vector<ll>(n / k + 2));
    for (int i = 0; i < n; ++i) {
        pref[i % k][i / k + 1] = pref[i % k][i / k] + a[i];
    }
    for (int i = 0; i < k; ++i) {
        while (pref[i].back() == 0) {
            pref[i].pop_back();
        }
    }

    auto get_l = [&](int i) {
        return pref[i % k][i / k + 1];
    };
    auto get_r = [&](int i) {
        return pref[i % k].back() - pref[i % k][i / k];
    };

    ll ans = 0;
    int p = -1, q = -1, pt = 0, qt = 0;
    for (auto i : a) {
        if (i < l - i) {
            p = max(p, i);
            pt++;
        } else {
            i = l - i;
            q = max(q, i);
            qt++;
        }
        if (pt == k) {
            ans += 2 * p;
            pt = 0; p = -1;
        }
        if (qt == k) {
            ans += 2 * q;
            qt = 0; q = -1;
        }
    }

    if (pt != 0) {
        ans += 2 * p;
    }
    if (qt != 0) {
        ans += 2 * q;
    }
    watch(ans);

    for (int i = 0; i + k <= n; ++i) {
        ll p = 0, q = 0;
        if (i > 0) {
            p = get_l(i - 1);
        }
        if (i + k < n) {
            q = get_r(i + k);
        }

        ans = min(ans, 2 * p + l + 2 * q);
    }



    return ans;
}

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