Submission #594592

#	Time	Username	Problem	Language	Result	Execution time	Memory
594592		skittles1412	Holiday (IOI14_holiday)	C++17	24 / 100	451 ms	65536 KiB

holiday

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long long long int
#define sz(x) int((x).size())

struct DS {
    vector<vector<long>> ans;

    DS(const vector<int>& arr) {
        for (int i = 0; i < sz(arr); i++) {
            vector<long> tmp(arr.begin(), arr.begin() + i + 1);
            sort(begin(tmp), end(tmp), greater<>());
            ans.emplace_back(i + 2);
            partial_sum(begin(tmp), end(tmp), ans[i].begin() + 1);
        }
    }

    long query(int i, int k) {
        if (k < 0) {
            return 0;
        }
        return ans[i][min(i + 1, k)];
    }
};

int m;

struct Pref {
    int mul;
    vector<int> arr;
    DS ds;
    vector<long> ans;

    Pref(int mul, const vector<int>& arr)
        : mul(mul), arr(arr), ds(arr), ans(m + 1) {}

    void dp(int l, int r, int ql, int qr) {
        if (l > r) {
            return;
        }
        int mid = (l + r) / 2;
        pair<long, int> opt {-1, -1};
        for (int i = ql; i <= qr; i++) {
            opt = max(opt,
                      pair<long, int> {ds.query(i, mid - (i + 1) * mul), -i});
        }
        auto& [cans, qmid] = opt;
        qmid = -qmid;
        ans[mid] = cans;
        dp(l, mid - 1, ql, qmid);
        dp(mid + 1, r, qmid, qr);
    }

    vector<long> solve() {
        if (sz(arr)) {
            dp(0, m, 0, sz(arr) - 1);
        }
        return ans;
    }
};

template <typename T>
T reversed(T t) {
    reverse(begin(t), end(t));
    return t;
}

long solve(int start, const vector<int>& arr) {
    auto suff =
        Pref(2, vector<int>(arr.begin() + start + 1, arr.end())).solve();
    auto pref = Pref(1, reversed(vector<int>(arr.begin(), arr.begin() + start)))
                    .solve();
    long ans = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j <= m; j++) {
            int k = m - j - i;
            if (k >= 0) {
                ans = max(ans, i * arr[start] + suff[j] + pref[k]);
            }
        }
    }
    return ans;
}

long findMaxAttraction(int n, int start, int _m, int inarr[]) {
    m = _m;
    vector<int> arr(inarr, inarr + n);
    return max(solve(start, arr), solve(n - start - 1, reversed(arr)));
}

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