Submission #1318530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318530		MisterReaper	Holiday (IOI14_holiday)	C++20	100 / 100	960 ms	5856 KiB

holiday

#include "holiday.h"
#include "bits/stdc++.h"

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

namespace {

int N;
int start;
int D;
std::vector<int> A;

int dist(int l, int r) {
    if (r < start) {
        return start - l;
    } else if (l <= start && start <= r) {
        return r - l + std::min(start - l, r - start);
    } else {
        return r - start;
    }
} 

i64 sum = 0;
std::multiset<i64> pql;
std::multiset<i64, std::greater<i64>> pqr;
i64 balance(int x) {
    x = std::max(0, x);
    while (!pqr.empty() && !pql.empty() && *pqr.begin() > *pql.begin()) {
        sum -= *pql.begin();
        pqr.emplace(*pql.begin());
        sum += *pqr.begin();
        pql.emplace(*pqr.begin());
        pql.erase(pql.begin());
        pqr.erase(pqr.begin());
    }
    while (int(pql.size()) > x) {
        sum -= *pql.begin();
        pqr.emplace(*pql.begin());
        pql.erase(pql.begin());
    }
    while (int(pql.size()) < x && !pqr.empty()) {
        sum += *pqr.begin();
        pql.emplace(*pqr.begin());
        pqr.erase(pqr.begin());
    }
    return sum;
};

int l = 0, r = -1;
i64 fit(int L, int R) {
    while (r < R) {
        pqr.emplace(A[++r]);
    }
    while (l > L) {
        pqr.emplace(A[--l]);
    }
    while (l < L) {
        if (pql.find(A[l]) != pql.end()) {
            sum -= A[l];
            pql.erase(pql.find(A[l]));
        } else {
            pqr.erase(pqr.find(A[l]));
        }
        l++;
    }
    while (r > R) {
        if (pql.find(A[r]) != pql.end()) {
            sum -= A[r];
            pql.erase(pql.find(A[r]));
        } else {
            pqr.erase(pqr.find(A[r]));
        }
        r--;
    }
    return balance(D - dist(l, r));
}

i64 ans = 0;

void dnq(int l, int r, int optl, int optr) {
    if (l > r) {
        return;
    }
    int mid = (l + r) >> 1;
    std::pair<i64, int> res = {0, optl};
    for (int i = optl; i <= std::min(optr, mid); ++i) {
        res = std::max(res, std::pair<i64, int>{fit(i, mid), i});
    }
    ans = std::max(ans, res.first);
    dnq(l, mid - 1, optl, res.second);
    dnq(mid + 1, r, res.second, optr);
};

};


i64 findMaxAttraction(int n, int start, int d, int attraction[]) {
    N = n;
    ::start = start;
    D = d;
    A.resize(N);
    for (int i = 0; i < N; ++i) {
        A[i] = attraction[i];
    }

    dnq(0, n - 1, 0, n - 1);

    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53