Submission #716869

#	Time	Username	Problem	Language	Result	Execution time	Memory
716869		vjudge1	Split the sequence (APIO14_sequence)	C++17	49 / 100	87 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e6 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll d[maxn];
ll dp[maxn];
vector< vector<int> > p;
void rec(int l, int r, int optl, int optr,int z) {
    if(l > r) return;
    int cur_best = optl;
    int m = (l + r)/2;
    dp[m] = d[cur_best] + pref[m] * pref[cur_best];
    for(int i = optl+1; i <= optr && i < m; i++) {
        if(dp[m] < d[i] + pref[m] * pref[i]) {
            dp[m] = d[i] + pref[m] * pref[i];
            cur_best = i;
        }
    }
    p[m][z] = cur_best;
    rec(l,m-1, optl, cur_best, z);
    rec(m+1, r, cur_best, optr, z);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    vector< vector<int> > P(n + 1, vector<int>(k+1, 0));
    p = P;
    for(int i = 1; i <= n; i++) {
        dp[i] = 0;
    }
    for(int it = 1; it <= k; it++) {
        int j = 0;
        for(int i = 0; i <= n; i++) {
            d[i] = dp[i]  - pref[i]*pref[i];
        }
        rec(it, n, it-1, n, it);
    }
    vector<int> cur;
    int last = n;

    for(int i = k; i >= 1; i--) {
        last = p[last][i];
        cur.push_back(last);
    }
    cout << dp[n] << "\n";
    reverse(cur.begin(), cur.end());
    for(int x: cur) cout << x << " ";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44:13: warning: unused variable 'j' [-Wunused-variable]
   44 |         int j = 0;
      |             ^

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