Submission #1087468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087468		Thunnus	Split the sequence (APIO14_sequence)	C++17	50 / 100	2091 ms	32860 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vi a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }

    vvi dp(n + 1, vi(k + 2)), from(n + 1, vi(k + 2));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k + 1; j++){
            for(int z = 0; z < i; z++){
                int val = dp[z][j - 1] + (a[i] - a[z]) * (a[n] - a[i]);
                if(val >= dp[i][j]){
                    from[i][j] = z;
                    dp[i][j] = val;
                }
            }
        }
    }

    cout << dp[n][k + 1] << "\n";
    vi ind;
    for(int i = k + 1, idx = n; i >= 1; i--){
		ind.emplace_back(idx);
        idx = from[idx][i];
    }
    for(int i = sz(ind) - 1; i >= 1; i--){
        cout << ind[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