Submission #989508

#	Time	Username	Problem	Language	Result	Execution time	Memory
989508		toan2602	Split the sequence (APIO14_sequence)	C++14	100 / 100	961 ms	82256 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define int long long
int n, k, a[100005], dp[2][100005], pfs2[100005];
int32_t trace[205][100005];
int cost(int l, int r) {
    return (pfs2[r] - pfs2[l-1]) * (pfs2[n] - pfs2[r]);
    //return pfs[r] - pfs[l - 1] - pfs2[l - 1] * (r - l + 1);
}

void solve(int l, int r, int opl, int opr, int k) {
    int mid = (l + r) / 2, res = -1, pos;
    for (int i = opl; i <= min(mid, opr); i++) if(i >= k) {
        int val = dp[k&1^1][i - 1] + cost(i, mid);
        if(res < val) {
            res = val;
            pos = i;
        }
    }
    dp[k&1][mid] = res;
    trace[k][mid] = pos - 1;
    if(l < mid) solve(l, mid-1, opl, pos, k);
    if(mid < r) solve(mid + 1, r, pos, opr, k);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k; ++k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pfs2[i] = pfs2[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[0][i] = -1;
    }
    for (int i = 1; i <= k; i++){
        memset(dp[i%2], -1, sizeof(dp[i%2]));
        solve(i, n, 1, n, i);
    }
    cout << dp[k%2][n] << endl;
    vector<int> ans;
    int p = n;
    for(int i = k; i > 1; i--){
        p = trace[i][p]; ans.push_back(p);
    }
    reverse(ans.begin(), ans.end());
    for(int i : ans) cout<<i<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:16:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   16 |         int val = dp[k&1^1][i - 1] + cost(i, mid);
      |                      ~^~
sequence.cpp:23:25: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     trace[k][mid] = pos - 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