Submission #678765

#	Time	Username	Problem	Language	Result	Execution time	Memory
678765		Romiros	Split the sequence (APIO14_sequence)	C++17	22 / 100	2086 ms	131072 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<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + 1, vector<ll>(k + 1)));
        vector<vector<vector<pair<int, int>>>> re(n + 1, vector<vector<pair<int, int>>>(n + 1, vector<pair<int, int>>(k + 1)));
        for (int cnt = 1; cnt <= k; cnt++){
            for (int l = n - cnt; l >= 1; l--){
                for (int r = l + cnt; r <= n; r++){
                    for (int i = l; i < r; i++){
                        for (int p = 0; p < cnt; p++){
                            int q = cnt - 1 - p;
                            if (dp[l][i][p] + dp[i + 1][r][q] + 
                                                (pref[r] - pref[i]) * 1ll * (pref[i] - pref[l - 1]) >= dp[l][r][cnt]){
                                dp[l][r][cnt] = max(dp[l][r][cnt], dp[l][i][p] + dp[i + 1][r][q] + 
                                            (pref[r] - pref[i]) * 1ll * (pref[i] - pref[l - 1]));
                                re[l][r][cnt] = {i, p};
                            }
                        }
                    }
                }
            }
        }
        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 = re[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;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < res.size(); i++){
      |                         ~~^~~~~~~~~~~~

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