Submission #1110154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110154		sunboi	Split the sequence (APIO14_sequence)	C++17	39 / 100	2066 ms	16464 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int INF = 1e18;


signed main(){
    int n, k; cin >> n >> k;
    vector<int> a(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = n; i >= 0; i--){
        suf[i] = suf[i + 1] + a[i];
    }
    
    vector<vector<int>> dp(n + 10, vector<int> (k + 1, 0));
    
    for (int i = n; i >= 1; i--){
        int l = i, r = n;
        while (r >= l) {
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
            int cost1 = (suf[l] - suf[mid1]) * suf[mid1];
            int cost2 = (suf[l] - suf[mid2]) * suf[mid2];
            if (cost1 > cost2) {
                r = mid2 - 1;
            }
            else if (cost1 < cost2) {
                l = mid1 + 1;
            }
            else {
                r = mid2 - 1;
                l = mid1 + 1;
            }
        }
        for (int j = i + 1; j <= l; j++){
            int suma = suf[i] - suf[j];
            int before = suf[j];
            for (int kk = 1; kk <= k; kk++){
                dp[i][kk] = max(dp[i][kk], dp[j][kk - 1] + suma * before);
            }
        }
    }
    set<int> id;
    
    int last = 1;
    int kk = k;
    for (int i = 2; i <= n; i++){
        
        int suma = suf[last] - suf[i];
        int before = suf[i];
        if (dp[last][kk] == dp[i][kk - 1] + suma * before){
            id.insert(i - 1);
            last = i;
            kk--;
        }
    }
    cout << dp[1][k] << endl;
    for (int x : id) cout << x << ' ';
    cout << endl;
    
    
}

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