Submission #960852

#	Time	Username	Problem	Language	Result	Execution time	Memory
960852		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	778 ms	81744 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;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        if(!pre[i])
            n--,zero[i--]++;
        else
            pre[i]+=pre[i-1],
            zero[i]+=zero[i-1];
    }
    if(k>=n-1){
        ll v=0;
        for(int i=1;i<n;i++)
            v+=((pre[n]-pre[i])*(pre[i]-pre[i-1]));
        cout<<v<<'\n';
        for(int i=1;i<n;i++)
            cout<<i+zero[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:47:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   47 |             while(ch.size()>1&&L.inter(ch[ch.size()-2])<=ch.back().inter(ch[ch.size()-2]))
      |             ^~~~~
sequence.cpp:48:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   48 |                 ch.pop_back(); ch.push_back(L);
      |                                ^~

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