Submission #1110104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110104		sunboi	Split the sequence (APIO14_sequence)	C++17	50 / 100	2041 ms	16488 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--){
        for (int j = i + 1; j <= n; 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++){
        //cout << last << ' ' << kk << endl;
        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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29