Submission #895964

#	Time	Username	Problem	Language	Result	Execution time	Memory
895964		gakshat468	Split the sequence (APIO14_sequence)	C++17	71 / 100	53 ms	131072 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll inf=1e9;
ll orientation(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){
    return (c.first-b.first)*(b.second-a.second)-(b.first-a.first)*(c.second-b.second);
    }

void solve(){
    int n, K;
    cin>>n>>K;
    vector<ll> a(n+1), p(n+1);
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        p[i]=p[i-1]+a[i];
        }

    vector<vector<ll>> dp(n+1, vector<ll>(K+1, -inf));
    for(ll i=1;i<=n;i++){
        dp[i][0]=0;
        }

    for(ll k=1;k<=K;k++){
        deque<pair<ll, ll>> ch;
        ch.push_back({ -1e9, -1e9 });
        for(ll i=1;i<=n;i++){
            //get max at p[i] in hull
            ll x=p[i];
            while(ch.size()>1ll&&ch[1].first*x+ch[1].second>=ch[0].first*x+ch[0].second){
                ch.pop_front();
                }
            dp[i][k]=max(dp[i][k], ch[0].first*x+ch[0].second);
            ll c=dp[i][k-1]-p[i]*p[i];
            ll m=p[i];
            while(ch.size()>1&&orientation(ch[ch.size()-2], ch[ch.size()-1], { m, c })<=0ll){
                ch.pop_back();
                }
            ch.push_back({ m, c });
            }
        }

    vector<ll> seq;
    for(ll k=K, i=n, j=n-1;k>=1;){
        if(dp[j][k-1]+(p[i]-p[j])*p[j]==dp[i][k]){
            seq.push_back(j);
            i=j;
            j--;
            k--;
            }
        else j--;
        }
    reverse(seq.begin(), seq.end());
    cout<<dp[n][K]<<endl;
    for(auto& i:seq)cout<<i<<" ";
    cout<<endl;
    }
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t=1;
    // cin>>t;
    while(t--){
        solve();
        }
    }

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