Submission #716843

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

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll dp[maxn][202];
int p[maxn][202];
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] = 0;
    }
    for(int it = 1; it <= k; it++) {
        int j = 0;
        for(int i = 1; i <= n; i++) {
            while(j + 1 < i && dp[j][it-1] + (pref[i] - pref[j]) * pref[j] <= dp[j+1][it-1] + (pref[i] - pref[j+1]) * pref[j+1]) {
                j++;
            }
            while(j - 1 >= 0 && dp[j][it-1] + (pref[i] - pref[j]) * pref[j] <= dp[j-1][it-1] + (pref[i] - pref[j-1]) * pref[j-1]) {
                j--;
            }
            p[i][it] = j;
            dp[i][it] = dp[j][it-1] + (pref[i] - pref[j]) * pref[j];
        }
    }
    vector<int> cur;
    int last = n;

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

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