Submission #1004779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004779		VMaksimoski008	Split the sequence (APIO14_sequence)	C++17	60 / 100	65 ms	131072 KiB

sequence

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

const int maxn = 1e5 + 5;

ll P[maxn+1], dp[maxn+1][205];
int par[maxn+1][205], n, K, v[maxn+1];

void f(int l, int r, int tl, int tr, int j) {
    if(l > r) return ;
    int tm = (l + r) / 2, p = tl;

    for(int i=tl; i<=min(tm, tr); i++) {
        ll v = dp[i-1][j-1] + (P[tm] - P[i-1]) * (P[n] - P[tm]);
        if(v > dp[tm][j]) {
            dp[tm][j] = v;
            par[tm][j] = i - 1;
            p = i;
        }
    }

    f(l, tm-1, tl, p, j);
    f(tm+1, r, p, tr, j);
}

int main() {
    cin >> n >> K;
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) P[i] = P[i-1] + v[i];
    for(int j=1; j<=K; j++) f(1, n, 1, n, j);

    int pos = 0;
    for(int i=1; i<n; i++)
        if(dp[i][K] >= dp[pos][K]) pos = i;
    
    cout << dp[pos][K] << '\n';
    int curr = pos, k = K;
    vector<int> ans;
    while(k) {
        ans.push_back(curr);
        curr = par[curr][k];
        if(k == 1) break;
        k--;
    }
    reverse(ans.begin(), ans.end());
    for(int &x : ans) cout << x << " ";
    return 0;
}

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