oj.uz

Submission #594666

# Submission time Handle Problem Language Result Execution time Memory
594666 2022-07-12T19:30:48 Z skittles1412 Holiday (IOI14_holiday) C++17
100 / 100
 4606 ms 60136 KB 
#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())

const int bsize = 1200, maxn = 1e5 + 5, maxb = maxn / bsize + 5;

struct DS {
    int n;
    vector<int> sorted[maxb];
    vector<long> spsum[maxb];
    vector<pair<long, int>> gaps[maxb];

    DS(const vector<int>& arr) : n(sz(arr)) {
        for (int i = 0, ind = 0; ind <= sz(arr); i++, ind += bsize) {
            sorted[i] = vector<int>(arr.begin(), arr.begin() + ind);
            sort(begin(sorted[i]), end(sorted[i]), greater<>());
            spsum[i].resize(sz(sorted[i]) + 1);
            for (int j = 0; j < sz(sorted[i]); j++) {
                spsum[i][j + 1] = spsum[i][j] + sorted[i][j];
            }
            for (int j = ind; j < min(sz(arr), ind + bsize); j++) {
                gaps[i].emplace_back(arr[j], j);
            }
            sort(begin(gaps[i]), end(gaps[i]), greater<>());
        }
    }

    long query(int i, int k) {
        if (k < 0) {
            return 0;
        }
        int ind = min(k, i + 1), bucket = i / bsize;
        long ans = 0;
        for (auto& [x, j] : gaps[bucket]) {
            if (!ind) {
                break;
            }
            if (j <= i) {
                if (ind - 1 >= sz(sorted[bucket]) || x > sorted[bucket][ind - 1]) {
                    ind--;
                    ans += x;
                } else {
                    break;
                }
            }
        }
        return ans + spsum[bucket][ind];
    }
};

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 684 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3582 ms 58184 KB Output is correct
2 Correct 4043 ms 58180 KB Output is correct
3 Correct 3555 ms 58160 KB Output is correct
4 Correct 4073 ms 58292 KB Output is correct
5 Correct 4278 ms 48336 KB Output is correct
6 Correct 1974 ms 9928 KB Output is correct
7 Correct 2519 ms 17372 KB Output is correct
8 Correct 2706 ms 23680 KB Output is correct
9 Correct 1654 ms 8912 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 928 KB Output is correct
2 Correct 94 ms 980 KB Output is correct
3 Correct 70 ms 948 KB Output is correct
4 Correct 94 ms 1108 KB Output is correct
5 Correct 83 ms 852 KB Output is correct
6 Correct 15 ms 756 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 9 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3752 ms 60136 KB Output is correct
2 Correct 4606 ms 59560 KB Output is correct
3 Correct 591 ms 7520 KB Output is correct
4 Correct 43 ms 724 KB Output is correct
5 Correct 8 ms 684 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 2047 ms 16776 KB Output is correct
9 Correct 2029 ms 17040 KB Output is correct