Submission #1207729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207729		jahongir	Split the sequence (APIO14_sequence)	C++20	50 / 100	882 ms	163416 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
                    tree_order_statistics_node_update>;

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()


struct Line{
    mutable ll m,c,p; mutable int ind; 
    bool operator<(const Line &o)const{return m<o.m;}
    bool operator<(ll x)const{return p<x;}
};

struct CHT : multiset<Line,less<>>{
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b){
        return a/b - ((a^b)<0 && a%b);
    }
    bool isect(iterator x, iterator y){
        if(y==end()) return x->p=inf,0;
        if(x->m==y->m) x->p = x->c > y->c ? inf : -inf;
        else x->p = div(x->c - y->c, y->m - x->m);
        return x->p>=y->p;
    }
    multiset<Line,less<>>::iterator x,y,z;
    void add(ll m, ll c, int ind){
        m = -m, c = -c;
        z = insert({m,c,0,ind}), y = z++, x = y;
        while(isect(y,z)) z = erase(z);
        if(x != begin() && isect(--x,y)) isect(x,y=erase(y));
        while((y=x) != begin() && (--x)->p >= y->p)
            isect(x,erase(y));
    }
    pair<ll,int> get(ll x){
        assert(!empty());
        auto l = *lower_bound(x);
        return {-(l.m * x + l.c),l.ind};
    }
};


const int mxn = 1e5+10;
const ll inf = 1e17;
ll arr[mxn];

int suc[mxn][201];


void solve(){
    int n,k; cin >> n >> k;

    CHT cht[k];

    for(int i = 1; i <= n; i++){
        cin >> arr[i]; arr[i] += arr[i-1];
    }

    for(int i = 1; i < k; i++) cht[i].add(0,inf,-1);
    cht[0].add(-2*arr[1],2*arr[1]*arr[1],1);

    ll ans = 0;

    for(int i = 2; i <= n; i++){
        for(int j = min(i,k); j >= 1; j--){
            auto [val,ind] = cht[j-1].get(arr[i]);
            ll tmp = val + arr[i]*arr[i];
            if(i==n && j==k) ans = tmp;
            suc[i][j] = ind;
            if(j!=k) cht[j].add(-2*arr[i],arr[i]*arr[i] + tmp,i);
        }
        cht[0].add(-2*arr[i],2*arr[i]*arr[i],i);
    }
    
    cout << (arr[n]*arr[n] - ans)/2 << '\n';
    
    vector<int> res;
    for(int u = suc[n][k], cnt = k; cnt>0; u = suc[u][--cnt])
        res.pb(u);

    reverse(all(res));
    for(auto x : res) cout << x << ' ';

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while(t--) solve();
}

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