Submission #997427

#	Time	Username	Problem	Language	Result	Execution time	Memory
997427		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	0 ms	348 KiB

beads

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

typedef long long ll;

const ll N = 1e4 + 100;
const ll K = 205;

ll n, k, a[N], dp[N][K], par[N][K], suff[N];

int main(){
    cin >> n >> k;
    k++;

    for (ll i = 1; i <= n; i ++)
        cin >> a[i];
    for (ll i = n; i > 0; i --)
        suff[i] = suff[i + 1] + a[i];

    for (ll p = 2; p <= k; p ++){
        int j = n - p + 2;
        for (ll i = n - p + 1; i > 0; i --){
            dp[i][p] = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
            par[i][p] = j;
            while (j - 1 > i and (dp[j - 1][p - 1] + (suff[i] - suff[j - 1]) * suff[j - 1]) >= dp[i][p]){
                j--;
                dp[i][p] = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
                par[i][p] = j;
                // cout << i << " " << p << " -- " << j << endl;
            }
            // cout << i << " " << p << " goes to " << j << " and val = " << dp[i][p] << endl;

            // for (ll j = i + 1; j <= n - p + 2; j ++){
            //     ll nval = dp[j][p - 1] + (suff[i] - suff[j]) * suff[j];
            //     // cout << i << " " << p << " goes to " << j << " and val = " << nval << endl;

            //     if (nval > dp[i][p])
            //         par[i][p] = j;

            //     dp[i][p] = max(dp[i][p], nval);
            // }
        }
    }

    cout << dp[1][k] << endl;

    int cur_i = 1;
    int cur_k = k;

    while (cur_k > 1){
        cout << par[cur_i][cur_k] - 1 << " ";
        cur_i = par[cur_i][cur_k];
        cur_k--;
    }
    cout << endl;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43