Submission #253131

#	Time	Username	Problem	Language	Result	Execution time	Memory
253131		LifeHappen__	Split the sequence (APIO14_sequence)	C++14	100 / 100	994 ms	83064 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)

#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define eb emplace_back
#define pb push_back

const int N=1e5+5;
long long n,a[N],k,s[N],x[N];
long long f[2][N];
int32_t best[201][N];
void dnc(int id, int l, int r, int u, int v) {
    if(l>r) return;
    int _=id&1;
    int mid=l+(r-l)/2;
    f[_][mid]=-1e15;
    forinc(i, u, min(mid - 1, v)) {
        if(f[_][mid]<=f[_^1][i]+(s[i]*(s[mid]-s[i]))){
            best[id][mid]=i;
            f[_][mid]=f[_^1][i]+(s[i]*(s[mid]-s[i]));
        }
    }
    dnc(id, l, mid - 1, u, best[id][mid]);
    dnc(id, mid + 1, r, best[id][mid], v);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    forinc(i,1,n) cin>>a[i];
    forinc(i,1,n) s[i]=s[i-1]+a[i];
    fordec(i,n,1) x[i]=x[i+1]+a[i];
    forinc(i,1,k){
        dnc(i, 1,n, 1,n);
    }
    cout<<f[k&1][n]<<'\n';
    vector<int> ans;
    int now=n;
    fordec(i,k,1){
        ans.pb(best[i][now]);
        now=best[i][now];
    }
    reverse(all(ans));
    forv(v, ans) cout << v << ' ';
}

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