Submission #934487

#	Time	Username	Problem	Language	Result	Execution time	Memory
934487		Darren0724	Split the sequence (APIO14_sequence)	C++17	100 / 100	525 ms	85708 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
const int INF=1e15;
const int mod=1e9+9;
struct Line{
    int a,b,id;
    int operator()(const int x){
        return a*x+b;
    }
};
bool check(Line l1,Line l2,Line l3){
    // int r1=(l1.b-l2.b)/(l2.a-l1.a);
    // int r2=(l1.b-l3.b)/(l3.a-l1.a);
    // return r2<=r1;
    return (l1.b-l3.b)*(l2.a-l1.a)<=(l1.b-l2.b)*(l3.a-l1.a);
}
int32_t main() {
    LCBorz;
    int n,k;cin>>n>>k;
    vector<int> v(n+1),pre(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        pre[i]=pre[i-1]+v[i];
    }
    vector dp(n+1,-INF);
    vector dp1(n+1,-INF);
    vector tran(k+1,vector(n+1,0));
    vector a(n+1,(int)0),b(n+1,(int)0);
    for(int j=1;j<=n;j++){
        dp[j]=(pre[n]-pre[j])*pre[j];
    }
    for(int i=2;i<=k;i++){
        deque<Line> dq;
        for(int j=0;j<=n;j++){
            a[j]=pre[n]+pre[j];
            b[j]=dp[j]-pre[n]*pre[j];
        }
        dq.push_back({pre[n],0,0});
        for(int j=1;j<=n;j++){
            while(dq.size()>=2&&dq[0](pre[j])<=dq[1](pre[j])){
                dq.pop_front();
            }
            dp1[j]=dq[0](pre[j])-pre[j]*pre[j];
            tran[i][j]=dq[0].id;
            Line l={a[j],b[j],j};
            while(dq.size()>=2&&check(dq.end()[-2],dq.end()[-1],l)){
                dq.pop_back();
            }
            dq.push_back(l);
        }
        dp=dp1;
        dp1.assign(n+1,-INF);
    }
    cout<<endl;
    int now=0;
    for(int i=1;i<n;i++){
        if(dp[i]>=dp[now])now=i;
    }
    cout<<dp[now]<<endl;
    for(int i=k;i>0;i--){
        cout<<now<<' ';
        now=tran[i][now];
    }
    cout<<endl;


    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