제출 #433151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433151		ngrace	수열 (APIO14_sequence)	C++14	0 / 100	50 ms	9620 KiB

sequence

#include <vector>
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ld long double
#define dq deque
#define pll pair<ll,ll>

struct line{
    ld m=0;
    ld c=0;
    ll ind=0;
};

ld inter(line a, line b){
    return (a.c-b.c)/(b.m-a.m);
}

dq<line> cht;
void add(ld m, ld c, ll ind){
    line x;
    x.m=m;
    x.c=c;
    x.ind=ind;
    while(cht.size()>1){
        line back=cht.back();
        cht.pop_back();
        ld one=inter(x,back);
        ld two=inter(back,cht.back());
        if(one>two){
            cht.push_back(back);
            break;
        }
    }
    cht.push_back(x);
}

line query(ll x){
    while(cht.size()>1){
        line front=cht.front();
        cht.pop_front();
        if(front.m*x + front.c > cht.front().m * x + cht.front().c){
            cht.push_front(front);
            break;
        }
    }
    return cht.front();
}

int main(){
    int N,K;
    cin>>N>>K;
    v<ll> vals(N);
    for(int i=0;i<N;i++) cin>>vals[i];
    v<ll> prefix;
    prefix.push_back(vals[0]);
    for(int i=1;i<N;i++) prefix.push_back(prefix.back() + vals[i]);

    v<v<int>> from(K+2,v<int>(N+2,-1));
    v<v<ll>> dp(K+2,v<ll>(N+2,0));
    for(int k=1;k<=K;k++){
        cht=dq<line>(0);
        for(int i=k-1;i<N-1;i++){
            if(i==0){
                dp[k][i]=prefix[i] * (prefix[N-1]-prefix[i]);
                from[k][i]=0;
                continue;
            }
            
            //add j=i to cht
            add(prefix[i-1], dp[k-1][i-1]- prefix[N-1] * prefix[i-1], i-1);
            //query x=prefix[i], also need to store j values in cht
            line q=query(prefix[i]);
            dp[k][i] = (prefix[i] * (prefix[N-1]-prefix[i])) + (q.m * prefix[i] + q.c);
            from[k][i] = q.ind;
            
            /**
            ll val=0;
            int ind=0;
            for(int j=k-1;j<=i;j++){
                ll tmp=prefix[i] * (prefix[N-1]-prefix[i]);
                tmp+=prefix[j-1]*prefix[i];
                tmp+=dp[k-1][j-1] - prefix[N-1] * prefix[j-1];
                val=max(val, tmp);
                if(val==tmp) ind=j-1;
            }
            dp[k][i]=val;
            from[k][i]=ind;**/
        }
    }

    ll out=0;
    int ind=0;
    for(int i=0;i<N-1;i++){
        out=max(out, dp[K][i]);
        if(out==dp[K][i]) ind=i;
    }
    
    cout<<out<<endl;
    for(int k=K;k>0;k--){
        cout<<ind+1<<" ";
        ind=from[k][ind];
    }
    cout<<endl;
}

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