Submission #1134235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134235		HappyCapybara	Split the sequence (APIO14_sequence)	C++20	100 / 100	680 ms	81860 KiB

sequence

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

#define int long long

int n, k;
vector<int> ps;
vector<vector<int>> dp;
vector<vector<signed>> best;

void compute(int l, int r, int optl, int optr, int kl){
    if (l > r) return;
    int m = (l+r)/2;
    pair<int,int> res = {-pow(10, 18), -1};
    for (int j=max(m+1, optl); j<=optr; j++){
        int cur = dp[1][j]+(ps[j]-ps[m])*(ps[n]-ps[j]);
        if (cur >= res.first) res = {cur, j};
    }
    dp[0][m] = res.first;
    best[kl][m] = res.second;
    int opt = res.second;
    compute(l, m-1, optl, opt, kl);
    compute(m+1, r, opt, optr, kl);
}

int solve(){
    for (int i=0; i<n; i++) dp[1][i] = 0;
    for (int i=1; i<=k; i++){
        compute(0, n-1, 0, n-1, i);
        dp[1] = dp[0];
    }
    return dp[0][0];
}

signed main(){
    cin.tie(0);
    iostream::sync_with_stdio(false);
    cin >> n >> k;
    ps.resize(n+1, 0);
    for (int i=0; i<n; i++){
        cin >> ps[i+1];
        ps[i+1] += ps[i];
    }
    dp.resize(2, vector<int>(n, -pow(10, 18)));
    best.resize(k+1, vector<signed>(n));
    cout << solve() << endl;
    int bruh = 0;
    for (int i=k; i>0; i--){
        cout << best[i][bruh] << " ";
        bruh = best[i][bruh];
    }
    cout << endl;
}

//dp[i][k] = max(dp[j][k-1]+(ps[j]-ps[i])*(ps[n]-ps[j]))
//ps[j]*ps[n]-ps[j]**2-ps[i]*ps[n]+ps[j]*ps[i]

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