Submission #711310

#	Time	Username	Problem	Language	Result	Execution time	Memory
711310		JJAnawat	Split the sequence (APIO14_sequence)	C++17	100 / 100	743 ms	84596 KiB

sequence

#include<bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
struct CHT{
    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 1.0*(c-l.c)/(l.m-m);
        }
    };
 
    deque<pair<line,double>> dq;
 
    void insert(ll mm,ll cc,int ii){
        line nline(mm,cc,ii);
 
        if(!dq.empty()&&dq.back().first.m==nline.m){
            if(nline.c>=dq.back().first.c)
                dq.pop_back();
            else
                return;
        }
 
        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<ll,int> query(ll 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;
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<ll,ll> 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 << 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:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | 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