Submission #939453

#	Time	Username	Problem	Language	Result	Execution time	Memory
939453		biximo	Split the sequence (APIO14_sequence)	C++17	89 / 100	711 ms	85076 KiB

sequence

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
struct Line {
    ll m,b;
    ll get(ll x) {
        return m*x+b;
    }
    long double cross(Line v) {
        return 1LL*(b-v.b)/(v.m-m);
    }
};
struct CHT {
    Line vt[N];
    int ind[N];
    int ft=0,bk=0;
    void adds(Line v, int i) {
        while(bk-ft) {
            if(vt[bk-1].m == v.m) {
                if(v.b < vt[bk-1].b) {
                    i = ind[bk-1];
                    v.b = vt[bk-1].b;
                }
                --bk;
            } else {
                break;
            }
        }
        while(bk-ft >= 2) {
            if(vt[bk-2].cross(v) < vt[bk-2].cross(vt[bk-1])) {
                --bk;
            } else {
                break;
            }
        }
        ind[bk] = i;
        vt[bk++] = v;
    }
    ll query(int x) {
        if(bk==ft) {
            assert(0);
        }
        while(bk-ft>=2) {
            if(vt[ft].cross(vt[ft+1]) < x) {
                ++ft;
            } else {
                break;
            }
        }
        return vt[ft].get(x);
    }
    void inits() {
        ft = 0, bk = 0;
    }
    CHT() {}
} cht;
ll n, k, pref[N], dp[N][2];
int bt[N][205];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        cin >> pref[i];
        pref[i] += pref[i-1];
    }
    ll ans = -1, ind;
    for(int j = 1; j <= k; j ++) {
        cht.inits();
        if(j == 1) {
            cht.adds({0,0},0);
        }
        for(int i = 1; i < j; i ++) {
            swap(dp[i][0],dp[i][1]);
            cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
        }
        for(int i = j; i <= n; i ++) {
            swap(dp[i][0],dp[i][1]);
            dp[i][1] = cht.query(pref[i])+pref[n]*pref[i]-pref[i]*pref[i];
            bt[i][j] = cht.ind[cht.ft];
            if(j == k && ans < dp[i][1]) {
                ind = i;
                ans = dp[i][1];
            }
            if(j > 1) {
                cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
            }
        }
    }
    assert(ind >= k);
    assert(ans != -1);
    vector<int> pt;
    int K = k;
    while(K) {
        pt.push_back(ind);
        ind = bt[ind][K--];
    }
    assert(!K);
    cout << ans << "\n";
    sort(pt.begin(),pt.end());
    for(int i: pt) cout << i << " ";
}

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