Submission #1148616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148616		blackslex	Split the sequence (APIO14_sequence)	C++20	0 / 100	1 ms	328 KiB

sequence

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, k;

int main() {
    scanf("%d %d", &n, &k);
    vector<int> a(n + 5), pref(n + 5);
    vector<vector<ll>> dp(k + 5, vector<ll>(n + 5));
    vector<vector<int>> par(k + 5, vector<int>(n + 5));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pref[i] = pref[i - 1] + a[i];
    }
    auto get = [&] (int l, int r) {
        return pref[r] - pref[l - 1];
    };
    for (int i = 1; i <= k + 1; i++) {
        for (int j = 1; j <= n; j++) {
            for (int l = 0; l < j; l++) {
                ll nval = dp[i - 1][l] + 1LL * get(l + 1, j) * get(j + 1, n);
                if (nval > dp[i][j]) {
                    dp[i][j] = nval;
                    par[i][j] = l;
                }
            }
        }
    }
    vector<pii> u{{k + 1, n}};
    while (u.back().first != 1) {
        auto [x, y] = u.back();
        u.emplace_back(x - 1, par[x][y]);
    }
    reverse(u.begin(), u.end()); u.pop_back();
    printf("%lld\n", dp[k + 1][n]);
    for (auto &[x, y]: u) {
        assert(y >= 1 && y <= n - 1);
        printf("%d ", y);
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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