Submission #262157

#	Time	Username	Problem	Language	Result	Execution time	Memory
262157		brcode	Split the sequence (APIO14_sequence)	C++14	100 / 100	734 ms	84344 KiB

sequence

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=205;
int n,k,a[N],q[N],pre[N][M];
long long pref[N],f[N],g[N];

double slope(int i,int j) {
    if(pref[i]==pref[j]) return -1e18;
    return 1.0*((g[i]-pref[i]*pref[i])-(g[j]-pref[j]*pref[j]))/(pref[j]-pref[i]);
}
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pref[i] = pref[i-1]+a[i];
    } 
    for(int j=1;j<=k;++j) {
        int l=1,r=1;
        q[r]=0;
        r++;
        for(int i=1;i<=n;++i) {
            while(l<r-1 && slope(q[l],q[l+1])<=pref[i]){
                l++;
            }
            f[i]=g[q[l]]+pref[q[l]]*(pref[i]-pref[q[l]]);
            pre[i][j]=q[l];
            while(l<r-1 &&slope(q[r-2],q[r-1])>=slope(q[r-1],i)) --r;
            q[r]=i;
            r++;
        }
        for(int i=1;i<=n;i++){
            g[i] = f[i];
            
        }
    }
    
    cout<<f[n]<<endl;
    int x=n;
    for(int i=k;i>=1;--i){
         x=pre[x][i];
         cout<<x<<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