Submission #1147102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147102		stanirina	Split the sequence (APIO14_sequence)	C++20	100 / 100	952 ms	86852 KiB

sequence

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

struct Line{
    int n,k;
    int eval(int x){return k*x+n;}
    int ix;
};

deque<Line> st;
int ind;

const int INF=numeric_limits<int>::min();

int query(int x){
    if(st.size()==0)return INF;
    while(st.size()>1){
        Line L=st.back();
        st.pop_back();
        if(L.eval(x)<=st.back().eval(x))continue;
        st.push_back(L);
        break;
    }
    ind=st.back().ix;
    return st.back().eval(x);
}

void add(Line L){
    if(st.empty()){
        st.push_front(L);
        return;
    }
    if(st.front().k==L.k){
        if(st.front().n>=L.n)return;
        else st.pop_front();
    }
    while(st.size()>=2){
        Line x=st.front();
        st.pop_front();
        if((L.n-x.n)*(st.front().k-x.k)>=(x.n-st.front().n)*(x.k-L.k))continue;
        st.push_front(x);
        break;
    }
    st.push_front(L);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++)cin>>v[i];

    vector<int> p(n);
    p[0]=v[0];
    for(int i=1;i<n;i++)p[i]=p[i-1]+v[i];

    vector<int> dp0(n,0);
    vector<int> dp1(n,0);
   // for(int l=0;l<n;l++)cout<<p[l]<<' ';
    //   cout<<endl;

    vector<vector<int32_t>> pos(n);
    for(int i=0;i<n;i++)pos[i].assign(k+2,-1);

    for(int i=0;i<n;i++)dp0[i]=p[i]*(p[n-1]-p[i]);
    //for(int l=0;l<n;l++)cout<<dp0[l]<<' ';
     //   cout<<endl;

    for(int j=2;j<=k+1;j++){
        st.clear();
        for(int i=1;i<n;i++){
            ind=-1;
            Line L;
            L.k=-p[i-1];
            L.n=dp0[i-1];
            L.ix=i-1;
            add(L);
            dp1[i]=query(p[n-1]-p[i])+p[i]*(p[n-1]-p[i]);
            pos[i][j]=ind;
        }
        //for(int l=0;l<n;l++)cout<<dp1[l]<<' ';
        //cout<<endl;
        for(int l=0;l<n;l++)dp0[l]=dp1[l];
    }

    cout<<dp0[n-1]<<endl;
    //for(int i=0;i<=k+1;i++){
      //  for(int j=0;j<n;j++)cout<<pos[j][i]<<' ';
     //   cout<<endl;
   // }
    int tr=n-1;
    for(int i=k+1;i>1;i--){
        cout<<pos[tr][i]+1<<' ';
        tr=pos[tr][i];
    }
    return 0;
}

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