Submission #1130120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130120		Art_ogo	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	468 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];

    vector<int> p, q;
    for (auto i : a) {
        if (l - i < i) {
            q.push_back(l - i);
        } else {
            p.push_back(i);
        }
    }

    sort(all(p), greater<>());
    sort(all(q));

    int left = n;
    ll ans = 0;
    while (left > 0) {
        bool ptaken = false, qtaken = false;
        ll s = 0;
        int plast = 0;
        for (int i = 0; i < k && left > 0; ++i) {
            if (!p.empty()) {
                s += p.back() - plast;
                ptaken = true;
                plast = p.back();
                p.pop_back();
                left--;
            } else {
                if (ptaken) {
                    if ((l - q.back()) - plast < q.back()) {
                        s += (l - q.back()) - plast;
                        plast = l - q.back();
                        q.pop_back();
                        left--;
                    } else {
                        break;
                    }
                } else {
                    if (!qtaken) {
                        s = q.back();
                    }
                    qtaken = true;
                    q.pop_back();
                    left--;
                }
            }
        }
        ans += min(2 * s, l);
    }

    cout << ans << '\n';
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:102:1: warning: no return statement in function returning non-void [-Wreturn-type]
  102 | }
      | ^

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