Submission #1269409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269409		rayan_bd	Split the sequence (APIO14_sequence)	C++20	0 / 100	88 ms	196608 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1001;
const int mxK = 201;
const int inf = -1e9;

int dp[mxN][mxN][mxK], ar[mxN], pref[mxN], n;

int query(int l, int r){
    if(l > r) return 0;
    return pref[r] - pref[l - 1];
}


int f(int i, int j, int k){
    if(k == 0) return 0;
    if(j > n) return inf;
    if(dp[i][j][k] != -1) return dp[i][j][k];
    int not_split = f(i, j + 1, k);
    int split = f(j + 1, j + 1, k - 1) + query(i, j) * query(j + 1, n);
    return dp[i][j][k] = max(not_split, split);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int k;

    cin >> n >> k;

    for(int i = 1; i <= n; ++i) cin >> ar[i];

    for(int i = 1; i <= n; ++i) pref[i] += pref[i - 1] + ar[i];

    memset(dp, -1, sizeof(dp));

    int best_answer = f(1, 1, k);

    //dp[i][j][k] = dp[i][j + 1][k] or dp[j + 1][j + 1][k - 1] + query(i, j) * query(j + 1, n);

    if(best_answer == 0){
        cout << best_answer << "\n";
        for(int i = 1; i <= k; ++i) cout << i << " ";
        cout << "\n";
        return 0;
    }


    int i = 1, j = 1;
    vector<int> ans;

    while(k > 0 && j < n){
        if(dp[i][j + 1][k] > (dp[j + 1][j + 1][k - 1] + query(i, j) * query(j + 1, n))){
            j += 1;
        }else{
            ans.push_back(j);
            i = ++j, --k;
        }
    }

    cout << best_answer << "\n";
    for(auto it : ans) cout << it << " ";
    cout << "\n";

    return 0;
}

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