Submission #1129336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129336		Hamed_Ghaffari	Split the sequence (APIO14_sequence)	C++20	100 / 100	1194 ms	82240 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))
#define mins(a, b) (a = min(a,b))
#define Mp make_pair
#define mid ((l+r)>>1)

const int MXN = 1e5+1;
const int MXK = 201;

int n, k, a[MXN], S[MXN];
ll P[MXN];

inline ll cost(int l, int r) {
    return P[r] - P[l-1] - ll(S[r]-S[l-1])*S[l-1];
}

ll dp[MXN], bef[MXN];
int par[MXN][MXK];

void divide(int x, int l=1, int r=n, int opl=1, int opr=n) {
    if(l>r) return;
    dp[mid] = 2e18;
    par[mid][x] = 0;
    for(int i=opl; i<=mid && i<=opr; i++) {
        ll res = bef[i-1]+cost(i, mid);
        if(res<=dp[mid]) {
            dp[mid] = res;
            par[mid][x]=i-1;
        }
    }
    divide(x, l, mid-1, opl, par[mid][x]+1);
    divide(x, mid+1, r, par[mid][x]+1, opr);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) {
        S[i] = S[i-1] + a[i];
        P[i] = P[i-1] + (ll)S[i-1]*a[i];
    }
    for(int i=1; i<=n; i++) dp[i] = cost(1, i);
    for(int i=1; i<=k; i++) {
        for(int j=1; j<=n; j++) bef[j] = dp[j];
        divide(i);
    }
    cout << P[n]-dp[n] << '\n';
    for(int t=k, i=par[n][k]; t>=1; i=par[i][--t])
        cout << i << ' ';
    cout << '\n';

    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