Submission #1129333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129333		Hamed_Ghaffari	Split the sequence (APIO14_sequence)	C++20	71 / 100	131 ms	196608 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

const int MXN = 1e5+2;
const int MXK = 202;

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

void input() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
}

void init() {
    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];
    }
}

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

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

void divide(int x, int l=1, int r=n, int opl=1, int opr=n) {
    if(l>r) return;
    int mid = (l+r)>>1;
    pll best = Mp(2e18, 0);
    for(int i=opl; i<=mid && i<=opr; i++)
        mins(best, pll(dp[i-1][x-1]+cost(i, mid), -i));
    best.second *= -1;
    dp[mid][x] = best.first;
    par[mid][x] = best.second-1;
    divide(x, l, mid-1, opl, best.second);
    divide(x, mid+1, r, best.second, opr);
}

void base() {
    for(int i=1; i<=n; i++) dp[i][0] = cost(1, i);
}

void solve() {
    base();
    for(int i=1; i<=k; i++) divide(i);
}

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

    input();
    init();
    solve();
    cout << P[n]-dp[n][k] << '\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: 0 / 29