Submission #711303

#	Time	Username	Problem	Language	Result	Execution time	Memory
711303		JJAnawat	Split the sequence (APIO14_sequence)	C++17	100 / 100	805 ms	84136 KiB

sequence

#include<bits/stdc++.h>

#define ll long long

using namespace std;

/*
struct CHT{
    struct line{
        int m,c,id;

        line(int mm=0,int cc=0,int i=0){
            m=mm;
            c=cc;
            id=i;
        }

        int cal(int x){
            return m*x+c;
        }

        double intersect(line l){
            return 1.0*(c-l.c)/(l.m-m);
        }
    };

    deque<pair<line,double>> dq;

    void insert(int m,int c,int i){
        line nline(m,c,i);

        while(dq.size()>1&&dq.back().second>=dq.back().first.intersect(nline))
            dq.pop_back();

        if(dq.empty())
            dq.push_back({nline,0});
        else
            dq.push_back({nline,nline.intersect(dq.back().first)});
    }

    pair<int,int> query(int x){
        while(dq.size()>1){
            if(dq[1].second<=x)
                dq.pop_front();
            else
                break;
        }
        return {dq.front().first.cal(x),dq.front().first.id};
    }

    void init(){
        dq.clear();
        insert(0,0,0);
    }
};
*/

struct line{
    ll m,c;
    int id;

    line(ll mm=0,ll cc=0,int i=0){
        m=mm;
        c=cc;
        id=i;
    }

    ll cal(ll x){
        return m*x+c;
    }

    double intersect(line l){
        return (c-l.c)/(l.m-m);
    }
};

int n,k;
ll s[100005];
int prv[100005][205];

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

    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> s[i];
        s[i]+=s[i-1];
    }
    vector<ll> dp(n+1,0),ndp(n+1,0);
    ++k;
    for(int j=1;j<=k;j++){
        /*
        CHT cht;
        cht.init();
        for(int i=1;i<=n;i++){
            pair<int,int> pi=cht.query(s[i]);
            ndp[i]=s[n]*s[i]-s[i]*s[i]+pi.first;
            prv[i][j]=pi.second;
            cht.insert(s[i],-s[i]*s[n]+dp[i],i);
        }
        dp=ndp;
        */
        deque<line> dq;
        dq.push_back(line());
        for(int i=1;i<=n;i++){
            while(dq.size()>1&&dq.back().cal(s[i])<=dq[dq.size()-2].cal(s[i]))
                dq.pop_back();
            ndp[i]=dq.back().cal(s[i])+s[n]*s[i]-s[i]*s[i];
            prv[i][j]=dq.back().id;
            line nline=line(s[i],-s[i]*s[n]+dp[i],i);
            if(!dq.empty()&&dq.front().m==nline.m){
                if(nline.c>=dq.front().c)
                    dq.pop_front();
                else
                    continue;
            }
            while(dq.size()>1&&nline.intersect(dq.front())<=dq[1].intersect(dq.front()))
                dq.pop_front();
            dq.push_front(nline);
        }
        dp=ndp;
    }
    cout << dp[n] << "\n";
    int cur=n;
    for(int j=k;j>=2;j--){
        cur=prv[cur][j];
        cout << cur << " ";
    }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~

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