Submission #960859

#	Time	Username	Problem	Language	Result	Execution time	Memory
960859		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	752 ms	81840 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed lead[100100][200],zero[100100];
int pre[100100],val[100100];
struct Ln{
    int k,b,ii;
    Ln(){k=b=0;}
    Ln(int a,int x,int i){k=a,b=x,ii=i;}
    int inter(Ln x){
        return (b-x.b)/(x.k-k);
    }
    int val(int x){
        return k*x+b;
    }
};
deque<Ln>ch;
signed 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]),
            n--,zero[i--]++;
        else
            pre[i]+=pre[i-1],
            zero[i]+=zero[i-1];
    }
    if(k>=n-1){
        int v=0;
        int x=k-n+1;
        while(st.size()>x)
            st.erase(st.begin());
        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++)
            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();
            int 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<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |         while(st.size()>x)
      |               ~~~~~~~~~^~
sequence.cpp:54:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   54 |             while(ch.size()>1&&L.inter(ch[ch.size()-2])<=ch.back().inter(ch[ch.size()-2]))
      |             ^~~~~
sequence.cpp:55:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   55 |                 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