Submission #711287

#	Time	Username	Problem	Language	Result	Execution time	Memory
711287		JJAnawat	Split the sequence (APIO14_sequence)	C++14	0 / 100	74 ms	131072 KiB

sequence

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int inf=1e18;

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);
    }
};

int n,k;
int 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<int> 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;
    }
    cout << ndp[n] << "\n";
    int cur=n;
    vector<int> v;
    for(int j=k;j>=2;j--){
        cur=prv[cur][j];
        v.push_back(cur);
    }
    while(!v.empty()){
        cout << v.back() << " ";
        v.pop_back();
    }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

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

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