Submission #472251

#	Time	Username	Problem	Language	Result	Execution time	Memory
472251		jalsol	Split the sequence (APIO14_sequence)	C++17	100 / 100	813 ms	82212 KiB

sequence

// looking to shine brighter in this world...

#define TASK "sequence"

#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

// copied from lacitirc

constexpr int maxn = 1e5 + 5;
constexpr int maxk = 200 + 5;

struct Line {
    int i;
    ll a, b;

    Line(int _i, ll _a, ll _b) : i(_i), a(_a), b(_b) {}

    ll f(ll x) {
        return a * x + b;
    }

    ld isect(const Line& o) {
        return ld(b - o.b) / (o.a - a);
    }
};

// intersect
// x.isect(z) <= x.isect(y)
// (x.b - z.b) / (z.a - x.a) <= (x.b - y.b) / (y.a - x.a)
bool bad(const Line& x, const Line& y, const Line& z) {
    return (x.b - z.b) * (y.a - x.a) <= (z.a - x.a) * (x.b - y.b);
}

struct Hull {
    deque<Line> q;

    void reset() {
        q.clear();
    }

    void add(const Line& l) {
        int sz = isz(q);
        while (sz >= 2 && bad(q[sz - 2], q[sz - 1], l)) {
            q.pop_back();
            --sz;
        }

        q.push_back(l);
    }

    int trace() {
        return q[0].i;
    }

    ll get(int x) {
        int sz = isz(q);
        while (sz >= 2 && q[0].f(x) <= q[1].f(x)) {
            q.pop_front();
            --sz;
        }

        return q[0].f(x);
    }
};

int n, k;
int a[maxn];
ll pref[maxn];

Hull hull[2];
ll dp[2][maxn];
int trace[maxk][maxn];

signed main() {
    cin >> n >> k;
    For (i, 1, n) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    int id = 0;
    For (j, 1, k) {
        hull[id ^ 1].reset();

        For (i, 1, n) {
            dp[id ^ 1][i] = hull[id].get(pref[i]);
            trace[j][i] = hull[id].trace();

            // a * (x - a) + b
            // ax + b - a^2
            hull[id].add({ i, pref[i], dp[id][i] - pref[i] * pref[i] });
        }

        id ^= 1;
    }

    cout << dp[id][n] << '\n';
    id = n;

    // order does not matter
    Ford (i, k, 1) {
        id = trace[i][id];
        cout << id << " \n"[i == 1];
    }

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29