Submission #670197

#	Time	Username	Problem	Language	Result	Execution time	Memory
670197		Mahdi	Split the sequence (APIO14_sequence)	C++17	100 / 100	1168 ms	81544 KiB

sequence

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int N=1e5+5;
int n, k, a[N], b[205][N], pd[N];
ll dp[N], dd[N];

void sol(int i, int l, int r, int lx, int rx){
    int m=(l+r)/2;
    pli x={dp[lx]+1LL*pd[lx]*(pd[m]-pd[lx]), lx};
    for(int j=lx+1;j<min(m, rx+1);++j)
        x=max(x, {dp[j]+1LL*pd[j]*(pd[m]-pd[j]), j});
    dd[m]=x.F;
    b[i][m]=x.S;
    if(l<m)
        sol(i, l, m, lx, x.S);
    if(m+1<r)
        sol(i, m+1, r, x.S, rx);
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pd[i]=a[i]+pd[i-1];
    }
    for(int i=1;i<=k;++i){
        sol(i, 1, n+1, 0, n-1);
        for(int j=1;j<=n;++j)
            dp[j]=dd[j];
    }
    cout<<dp[n]<<'\n';
    vector<int>v;
    int h=n;
    for(int i=k;i>0;--i){
        h=b[i][h];
        v.push_back(h);
    }
    for(int i=k-1;i>=0;--i)
        cout<<v[i]<<' ';
    cout<<'\n';
}

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