제출 #1146743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146743		stanirina	수열 (APIO14_sequence)	C++20	71 / 100	2098 ms	98888 KiB

sequence

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

using namespace std;

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

vector<Line> st;
vector<int> b;
int ind;

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

void add(int node, int l, int r, Line L){
    if(!st[node].act){
        st[node]=L;
        return;
    }
    int rold=st[node].eval(b[r]), rnew=L.eval(b[r]);
    int lold=st[node].eval(b[l]), lnew=L.eval(b[l]);

    if(lold>=lnew && rold>=rnew)return;
    if(lold<lnew && rold<rnew){
        st[node]=L;
        return;
    }
    if(lold<lnew)swap(L,st[node]);
    int mid=(l+r)/2;
    if(L.eval(b[mid])<=st[node].eval(b[mid])){
        add(node*2+1,mid+1,r,L);
        return;
    }
    else{
        add(node*2,l,mid,st[node]);
        st[node]=L;
        return;
    }
}

int query(int node, int l, int r, int x){
    if(!st[node].act)return INF;
    if(l==r){ind=st[node].ix;return st[node].eval(x);}
    int mid=(l+r)/2;
    int sol=st[node].eval(x);
    ind=st[node].ix;
    if(x<=b[mid]){
        int ans=query(node*2,l,mid,x);
        if(ans<=sol)ind=st[node].ix;
        sol=max(sol,ans);
    }
    else{
        int ans=query(node*2+1,mid+1,r,x);
        if(ans<=sol)ind=st[node].ix;
        sol=max(sol,ans);
    }
    return sol;
}

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);

    b.resize(n);
    for(int i=0;i<n;i++)b[i]=p[n-1]-p[n-1-i];
    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();
        st.resize(4*n);
        for(int i=1;i<n;i++){
            ind=-1;
            Line L;
            L.act=true;
            L.k=-p[i-1];
            L.n=dp0[i-1];
            L.ix=i-1;
            add(1,0,n-1,L);
            dp1[i]=query(1,0,n-1,p[n-1]-p[i])+p[i]*(p[n-1]-p[i]);

            pos[i][j]=ind;//cout<<1<<endl;
        }
        //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: 0 / 29