Submission #572639

#	Time	Username	Problem	Language	Result	Execution time	Memory
572639		stevancv	Split the sequence (APIO14_sequence)	C++14	100 / 100	1413 ms	81484 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
int mod = 1000000007;
int prv[N][200];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    vector<ll> dp(n + 1);
    for (int i = 1; i <= k; i++) {
        vector<ll> ndp(n + 1);
        function<void(int, int, int, int)> Solve = [&] (int l, int r, int opl, int opr) {
            if (l > r) return;
            ll val = -1e18;
            int best = 0;
            int mid = l + r >> 1;
            for (int j = opl; j <= min(opr, mid); j++) {
                ll x = dp[j - 1] + a[j - 1] * (a[mid] - a[j - 1]);
                if (x >= val) {
                    val = x;
                    best = j;
                }
            }
            prv[mid][i] = best;
            ndp[mid] = val;
            Solve(l, mid - 1, opl, best);
            Solve(mid + 1, r, best, opr);
        };
        Solve(1, n, 1, n);
        swap(dp, ndp);
    }
    cout << dp[n] << en;
    vector<int> ans;
    int j = n;
    for (int i = k; i >= 1; i--) {
        ans.push_back(prv[j][i] - 1);
        j = prv[j][i] - 1;
    }
    while (!ans.empty()) {
        cout << ans.back() << sp;
        ans.pop_back();
    }
    cout << en;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:30:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |             int mid = l + r >> 1;
      |                       ~~^~~

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