Submission #231913

#	Time	Username	Problem	Language	Result	Execution time	Memory
231913		parsa_mobed	Split the sequence (APIO14_sequence)	C++14	100 / 100	1602 ms	82680 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5, K = 201;
int a[N], par[N][K], lvl;
long long dp[N][2], C[N], ps[N];

long long Cost(int l, int r) {return C[r] - C[l - 1] - (ps[r] - ps[l - 1]) * ps[l - 1];}
void Solve(int s, int e, int l, int r) {
    if (s == e) return ;
    int mid = (s+e)>>1, pos = l;
    dp[mid][lvl&1] = dp[l - 1][lvl&1^1] + Cost(l, mid);
    for (int i = l + 1; i <= min(mid, r); i++)
        if (dp[i - 1][lvl&1^1] + Cost(i, mid) <= dp[mid][lvl&1]) dp[mid][lvl&1] = dp[i - 1][lvl&1^1] + Cost(i, mid), pos = i;
    par[mid][lvl] = pos - 1;
    Solve(s, mid, l, pos), Solve(mid + 1, e, pos, r);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], dp[i][0] = C[i] = C[i - 1] + a[i] * ps[i - 1], ps[i] = ps[i - 1] + a[i];
    for (lvl = 1; lvl <= k; lvl++) Solve(1, n + 1, 1, n);
    cout << C[n] - dp[n][k&1] << "\n";
    vector <int> ans;
    while (par[n][k]) ans.push_back(n = par[n][k]), k--;
    reverse(ans.begin(), ans.end());
    for (int i : ans) cout << i << " ";
    cout << "\n";

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void Solve(int, int, int, int)':
sequence.cpp:12:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     dp[mid][lvl&1] = dp[l - 1][lvl&1^1] + Cost(l, mid);
                                ~~~^~
sequence.cpp:14:26: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         if (dp[i - 1][lvl&1^1] + Cost(i, mid) <= dp[mid][lvl&1]) dp[mid][lvl&1] = dp[i - 1][lvl&1^1] + Cost(i, mid), pos = i;
                       ~~~^~
sequence.cpp:14:96: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         if (dp[i - 1][lvl&1^1] + Cost(i, mid) <= dp[mid][lvl&1]) dp[mid][lvl&1] = dp[i - 1][lvl&1^1] + Cost(i, mid), pos = 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