Submission #138214

#	Time	Username	Problem	Language	Result	Execution time	Memory
138214		Runtime_error_	Split the sequence (APIO14_sequence)	C++14	71 / 100	499 ms	131076 KiB

sequence

//APIO 2014 Split the sequence
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e5+9,K=209,MX=1e9+9;
ll n,k,ans=-MX,idx;
ll pre[inf],a[inf];
pair<ll,ll> dp[K][inf];
vector<ll> split;


struct line {
    ll m, c,idx;
    ll eval(ll x) { return m * x + c; }
    #define ld long double
    ld intersectX(line l) {
        assert(l.m != m);
         return (ld) (c - l.c) / (l.m - m);
         }
};

struct LineContainer{
    //for maximum
    // m increasing and x increasing
    //to get m is decreasing x is decreasing -m , -x

    deque<line> dq;
    #define last dq.size()-1

    void add(ll m,ll p,ll idx){
        line cur = {m,p,idx};
        while (dq.size() >= 2 && dq[last-1].intersectX(cur) <= dq[last-1].intersectX(dq[last]))
            dq.pop_back();
        dq.push_back(cur);
    }

    pair<ll,ll> query(ll x){
        while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x))
            dq.pop_front();

        return make_pair(dq[0].eval(x),dq[0].idx);
    }
};

int main(){

    cin>>n>>k;
    for(ll i=1;i<=n;i++)
        cin>>a[i],pre[i]=pre[i-1]+a[i];

    for(ll j=1;j<=k;j++){
        LineContainer lc;
        lc.add(pre[j-1],dp[j-1][j-1].first - pre[j-1]*pre[n],j-1);
        for(ll i=j;i<=n;i++){
            dp[j][i] = lc.query(pre[i]);
            dp[j][i].first += pre[i]*pre[n] - pre[i]*pre[i] ;
            lc.add(pre[i],dp[j-1][i].first-pre[i]*pre[n],i);
        }
    }

    for(ll i=1;i<=n;i++)
        if(ans<dp[k][i].first)
            ans=dp[k][i].first,idx=i;

    split.push_back(idx);
    for(ll j=k;j>1;j--)
        idx=dp[j][idx].second,split.push_back(idx);

    reverse(split.begin(),split.end());

    cout<<ans<<endl;
    for(auto o:split)
        cout<<o<<" ";
    cout<<endl;
}

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