Submission #960997

#	Time	Username	Problem	Language	Result	Execution time	Memory
960997		boyliguanhan	Split the sequence (APIO14_sequence)	C++17	100 / 100	758 ms	82036 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int lead[100100][200],zero[100100];
ll pre[100100],val[100100];
struct Ln{
    ll k,b,ii;
    Ln(){k=b=0;}
    Ln(ll a,ll x,ll i){k=a,b=x,ii=i;}
    ll inter(Ln x){
        return (b-x.b)/(x.k-k);
    }
    ll val(int x){
        return k*x+b;
    }
};
deque<Ln>ch;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    set<int>st;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        if(!pre[i])
            st.insert(i+zero[i-1]+zero[i]),
            n--,zero[i--]++;
        else
            pre[i]+=pre[i-1],
            zero[i]+=zero[i-1];
    }
    if(k>=n-1){
        ll v=0;
        int x=k-n+1;
        while(st.size()>x)
            st.erase(st.begin());
        for(int i=2;i<=n;i++)
            v+=(pre[i]-pre[i-1])*pre[i-1];
        cout<<v<<'\n';
        for(int i=1;i<n;i++)
            st.insert(i+zero[i]);
        for(auto i:st)
            cout<<i<<' ';
        return 0;
    }
    for(int i=1;i<=k;i++){
        ch.push_back(Ln(pre[i],val[i]-pre[i]*pre[i],i));
        for(int j=i+1;j<=n;j++){
            while(ch.size()>1&&ch[0].inter(ch[1])<pre[j])
                ch.pop_front();
            ll V=ch[0].val(pre[j]);
            lead[j][i]=ch[0].ii;
            Ln L(pre[j],val[j]-pre[j]*pre[j],j);
            while(ch.size()>1&&L.inter(ch[ch.size()-2])<ch.back().inter(ch[ch.size()-2]))
                ch.pop_back();
            ch.push_back(L),val[j]=V;
        }
        ch.clear();
    }
    cout<<val[n]<<'\n';
    stack<int>stk;
    int cnt=k+1;
    while(--cnt)
        stk.push(n=lead[n][cnt]);
    while(stk.size())
        cout<<stk.top()+zero[stk.top()]<<' ',stk.pop();
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:35:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         while(st.size()>x)
      |               ~~~~~~~~~^~

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