Submission #670248

#	Time	Username	Problem	Language	Result	Execution time	Memory
670248		fatemetmhr	Split the sequence (APIO14_sequence)	C++17	100 / 100	413 ms	84664 KiB

sequence

// hmmm... na dige chizi baraye goftan namoonde


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e5 + 10;
const int maxk  = 203;
const ll  inf   = 1e18;

struct __cht{

    int sz, pt;
    pair <pair<ll, int>, pair<ll, ll>> a[maxn5]; // {{start, ind}, {const, shib}}

    void clear(){
        sz = pt = 0;
    }

    ll inter(pair<ll, ll> a, pair<ll, ll> b){
        if(a.se == b.se)
            return a.fi > b.fi ? inf : -inf;
        return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
    }

    void add(ll c, ll s, int id){
        while(sz && inter(a[sz - 1].se, {c, s}) <= a[sz - 1].fi.fi)
            sz--;
        a[sz] = {{-inf, id}, {c, s}};
        if(sz)
            a[sz].fi.fi = inter(a[sz - 1].se, a[sz].se);
        sz++;
    }

    pair<ll, int> get_max(ll x){
        while(pt + 1 < sz && a[pt + 1].fi.fi <= x)
            pt++;
        return {a[pt].se.fi + a[pt].se.se * x, a[pt].fi.se};
    }

} cht;

ll ps[maxn5], dp[2][maxn5];
int par[maxk][maxn5];
bool mark[maxn5];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> n >> k;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        ps[i] = a + (i ? ps[i - 1] : 0);
    }

    for(int t = 1; t <= k; t++){
        cht.clear();
        cht.add(0, 0, -1);
        for(int i = 0; i < n; i++){
            auto tmp = cht.get_max(ps[i]);
            dp[t&1][i] = tmp.fi;
            par[t][i] = tmp.se;
            cht.add(dp[(t&1)^1][i] - ps[i] * ps[i], ps[i], i);
        }
    }

    cout << dp[k&1][n - 1] << endl;

    int v = n - 1, t = k;
    while(t){
        if(par[t][v] == -1)
            break;
        cout << par[t][v] + 1 << ' ';
        v = par[t][v];
        mark[v] = true;
        t--;
    }
    for(int i = 0; i < n && t; i++) if(!mark[i]){
        cout << i + 1 << ' ';
        t--;
    }
    cout << endl;

}

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