Submission #836567

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

sequence

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+5;
const int K=205;

int n,k;
int a[N];
ll qs[N],dp[K][N];
int opt[K][N];

struct convexhull{
    struct line{
        ll m,c;
        int id;
        line(){}
        line(ll m,ll c,int id):m(m),c(c),id(id){}
        ll get(ll x){
            return m*x+c;
        }
    };
    bool bad(line l1,line l2,line l3){
        return (l1.c-l2.c)*(l3.m-l1.m)>=(l1.c-l3.c)*(l2.m-l1.m);
    }
    deque<line> hull;
    void init(){
        hull.clear();
    }
    void insert(ll m,ll c,int id){
        line l(m,c,id);
        while(hull.size()>1&&bad(hull.end()[-2],hull.back(),l))hull.pop_back();
        hull.emplace_back(l);
    }
    pair<ll,int> query(ll x){
        while(hull.size()>1&&hull[1].get(x)>=hull[0].get(x))hull.pop_front();
        return {hull[0].get(x),hull[0].id};
    }
}hull;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=n;i++)qs[i]=qs[i-1]+a[i];
    for(int i=1;i<=n;i++)dp[1][i]=qs[i]*(qs[n]-qs[i]);
    for(int i=2;i<=k;i++){
        hull.init();
        for(int j=1;j<=n;j++){
            if(j>i){
                auto [val,id]=hull.query(qs[j]);
                dp[i][j]=qs[j]*(qs[n]-qs[j])+val;
                opt[i][j]=id;
            }
            hull.insert(qs[j],-qs[j]*qs[n]+dp[i-1][j],j);
        }
    }
    ll ans=0;
    int id=0;
    for(int i=1;i<=n;i++){
        if(dp[k][i]>ans){
            ans=dp[k][i];
            id=i;
        }
    }
    vector<int> res;
    for(int i=k;i>=1;i--){
        res.emplace_back(id);
        id=opt[i][id];
    }
    reverse(res.begin(),res.end());
    cout << ans << "\n";
    for(auto x:res)cout << x << " ";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:53:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |                 auto [val,id]=hull.query(qs[j]);
      |                      ^

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