Submission #857926

#	Time	Username	Problem	Language	Result	Execution time	Memory
857926		nammm	Split the sequence (APIO14_sequence)	C++14	100 / 100	1041 ms	82584 KiB

sequence

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define vi vector<int>
using namespace std;
const int N=1e5+5;
int par[1201][N]{0};
ll d1[N]{0},d2[N]{0};
ll a[N]{0};
int n;
int cur=1;
void solve(int l,int r,int opl,int opr){
    int m=(l+r)>>1;
    pll t = {0,0};
    for(int i=opl;i<=min(opr,m-1);i++){
        t=max(t,{d1[i]+(a[m]-a[i])*(a[n]-a[m]),i});
    }
    par[cur][m]=t.s;
    d2[m]=t.f;
    if(l>=r)return;
    solve(l,m-1,opl,t.s),solve(m+1,r,t.s,opr);

}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=k;i++){
        solve(i,n,i-1,n);
        for(int i=1;i<=n;i++)d1[i]=d2[i];
        cur++;
    }ll ans=0;
    int mem;
    for(int i=1;i<=n;i++){
        if(ans<d2[i])ans=d2[i],mem=i;
    }cout<<ans<<"\n";
    if(ans==0){cout<<1;return 0;}
    stack<int>st;
    while(cur>1){
        cur--;
        st.push(mem);
        mem=par[cur][mem];
    }
    while(!st.empty())cout<<st.top()<<" ",st.pop();
}

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