Submission #1207704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207704		jahongir	Split the sequence (APIO14_sequence)	C++20	22 / 100	3 ms	2632 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 int ll
#define all(a) a.begin(),a.end()


struct Line{
    mutable ll m,c,p, 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;
    }
    void add(ll m, ll c, ll ind){
        m = -m, c = -c;
        auto 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,ll> 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 = 1e15;
int arr[mxn];

ll dp[mxn][201];
int suc[mxn][201];

void apply(ll &a, ll b){a=min(a,b);}

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];
        dp[i][0] = arr[i]*arr[i];
        cht[0].add(-2*arr[i],arr[i]*arr[i]+dp[i][0],i);
    }

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

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

    while(u){
        res.pb(u); u = suc[u][--cnt];
    }

    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: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29