Submission #678772

#	Time	Username	Problem	Language	Result	Execution time	Memory
678772		Romiros	Split the sequence (APIO14_sequence)	C++17	50 / 100	2081 ms	24660 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define vi vector<int>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef ON_PC
        freopen("input.txt", "r", stdin);
    #endif
    // freopen("output.txt", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--){
        int n, k;
        cin >> n >> k;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        vector<ll> pref(n + 1);
        for (int i = 1; i <= n; i++){
            pref[i] = pref[i - 1] + a[i];
        }
        vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -1e18));
        vector<vector<int>> p(n + 1, vector<int>(k + 1));
        for (int i = 1; i <= n; i++){
            dp[i][0] = 0;
        }
        for (int cnt = 1; cnt <= k; cnt++){
            for (int i = 1; i <= n; i++){
                for (int j = i - 1; j >= 1; j--){
                    if (dp[j][cnt - 1] != -1e18 && 
                        dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]) >= dp[i][cnt]){
                        p[i][cnt] = j;
                        dp[i][cnt] = max(dp[i][cnt], dp[j][cnt - 1] + (pref[n] - pref[i - 1]) * 1ll * (pref[i - 1] - pref[j - 1]));
                    }
                }
            }
        }
        int v = 1;
        for (int i = 1; i <= n; i++){
            if (dp[i][k] > dp[v][k]){
                v = i;
            }
        }
        cout << dp[v][k] << "\n";
        vector<int> res;
        for (int cnt = k; cnt >= 1; cnt--){
            res.push_back(v);
            v = p[v][cnt];
        }
        reverse(all(res));
        for (int i = 0; i < k; i++){
            cout << res[i] - 1 << " ";
        }
        cout << "\n";
        // cout << dp[1][n][k] << "\n";
        // vector<int> res;
        // queue<array<int, 3>> q;
        // q.push({1, n, k});
        // while (!q.empty()){
        //     array<int, 3> t = q.front();
        //     q.pop();
        //     pair<int, int> w = p[t[0]][t[1]][t[2]];
        //     res.push_back(w.first);
        //     if (t[2]){
        //         q.push({t[0], w.first, w.second});
        //         q.push({w.first + 1, t[1], t[2] - 1 - w.second});
        //     }
        // }
        // assert(!res.empty());
        // sort(all(res));
        // for (int i = 0; i < res.size(); i++){
        //     if (res[i]){
        //         cout << res[i] << " "; 
        //     }
        // }
        // cout << "\n";
    }
    return 0;
}

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