Submission #1269407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269407		rayan_bd	Split the sequence (APIO14_sequence)	C++20	Compilation error	0 ms	0 KiB

sequence

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

const int mxN = 205;
const int mxK = 205;
const int inf = -1e9;

#define int long long

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;
    }


    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;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:49:9: error: return-statement with no value, in function returning 'int' [-fpermissive]
   49 |         return;
      |         ^~~~~~