Submission #1129015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129015		crafticat	Candies (JOI18_candies)	C++17	100 / 100	826 ms	22268 KiB

candies

#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;
#define f first
#define s second
#define F0R(i,n) for(ll i = 0; i < n;i++)
#define FOR(i,j,n) for(ll i = j; i < n;i++)
using ll = long long;

constexpr ll INF = 1e15;
using vi = V<ll>;

vi arr;

vi combine(vi a, vi b, ll targetSize) {
    a.resize(targetSize, -INF);
    b.resize(targetSize, -INF);
    vi c(targetSize, -INF);

    int l = 0, r = 0;
    F0R(i, targetSize) {
        c[i] = a[l] + b[r];
        if (a[l + 1]- a[l] > b[r + 1] - b[r]) {
            l++;
        } else
            r++;
    }
    return c;
}

V<V<vi>> solve(ll l, ll r) {
    V<V<vi>> ans(2, V<vi>(2, vi(r - l + 1, -INF)));
    if (r - l <= 1) {
        ans[0][0][0] = 0;
        ans[1][1][1] = arr[l];
        return ans;
    }

    ll mid = (l + r) / 2;
    V<V<vi>> left = solve(l, mid), right = solve(mid, r);
    F0R(i, 2) {
        F0R(j, 2) {
            F0R(k, 2) {
                F0R(t, 2) {
                    if (k & t) continue;
                    vi res = combine(left[i][k], right[t][j], r - l + 1);

                    ll iter = 0;
                    for (auto &v : ans[i][j])
                        v = max(v, res[iter++]);
                }
            }
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll n; cin >> n;
    arr.resize(n);
    F0R(i, n)
        cin >> arr[i];

    V<V<vi>> res = solve(0, n);
    FOR(i, 1, ((n + 1) / 2) + 1) {
        ll best = 0;
        F0R(j, 2) {
            F0R(k, 2) {
                best = max(best, res[j][k][i]);
            }
        }
        cout << best << "\n";
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92