Submission #716870

#	Time	Username	Problem	Language	Result	Execution time	Memory
716870		vjudge1	Split the sequence (APIO14_sequence)	C++17	100 / 100	937 ms	81516 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];
int p[202][100100];
inline 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[z][m] = 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];
    }
    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[i][last];
        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:42:13: warning: unused variable 'j' [-Wunused-variable]
   42 |         int j = 0;
      |             ^

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