Submission #1000951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000951		vjudge1	Split the sequence (APIO14_sequence)	C++17	100 / 100	642 ms	87284 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Line{
    i64 m, c, idx;

    Line(i64 m = 0, i64 c = 0, i64 idx = 0) : m(m), c(c), idx(idx) {}

    i64 operator ()(i64 x){ return m * x + c; }

    long double operator ^(const Line &t){
        return (c - t.c + .0) / (t.m - m);
    }

    bool isOpt(Line ff, Line ss){
        __int128 p = c - ff.c, q = c - ss.c;
        p *= ss.m - m, q *= ff.m - m;
        return p <= q;
    };
};

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

    int n, k; cin >> n >> k;

    vector <i64> a(n), pf(n + 1);

    for ( auto &u: a ){
        cin >> u;
    }

    for ( int i = 0; i < n; i++ ){
        pf[i + 1] = pf[i] + a[i];
    }

    vector <vector<int>> fa(n + 1, vector <int> (k + 1));

    vector <i64> dp(n + 1);

    for ( int j = 1; j <= k; j++ ){
        auto nxt = dp;

        deque <Line> dq;

        auto ins = [&](int j){
            Line nw = {pf[j], dp[j] - pf[j] * pf[j], j};

            while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(nw, dq.back()) ){
                dq.pop_back();
            }

            dq.pb(nw);
        };

        ins(0);

        for ( int i = 1; i <= n; i++ ){
            while ( dq.size() > 1 && dq[0](pf[i]) <= dq[1](pf[i]) ){
                dq.pop_front();
            }

            nxt[i] = dq[0](pf[i]);

            fa[i][j] = dq[0].idx;

            ins(i);
        }

        swap(dp, nxt);
    }

    vector <int> ans;

    int x = n;

    for ( int i = k; i > 0; i-- ){
        ans.pb(fa[x][i]);

        x = fa[x][i];
    }

    reverse(all(ans));

    cout << dp.back() << ln;

    for ( auto &u: ans ){
        cout << u << ' ';
    }

    cout << '\n';
}

/*

7 3
4 1 3 4 0 2 3

*/

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