52172023-04-22 20:05:20sztomiMajomházcpp17Runtime error 10/1003.101s524700 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
vector<vector<vector<ll>>> dp;
vector<ll> pref_sum;
vector<int> a;

ll resz_osszeg(int i, int j){
    return (pref_sum[j] - pref_sum[i-1]) * (j-i+1);
}

ll megold(int elso, int akt, int db){
    if(akt == n){
        return resz_osszeg(elso, n);
    }
    if(db == 0){
        return resz_osszeg(elso, n);
    }

    if(dp[elso][akt][db] != -1){
        return dp[elso][akt][db];
    }

    ll ki = megold(elso, akt+1, db);
    ki = min(ki, megold(akt+1, akt+1, db-1) + resz_osszeg(elso, akt));

    return ki;

}

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);

    cin >> n >> k;
    dp.assign(n+1, vector<vector<ll>>(n+1, vector<ll>(k+1, -1)));
    a.resize(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    pref_sum.resize(n+1);
    pref_sum[0] = 0;
    for(int i = 1; i <= n; i++){
        pref_sum[i] = pref_sum[i-1] + a[i];
    }

    ll ret = megold(1, 1, k);

    cout << ret << "\n";

}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1820 KiB
2Runtime error214ms524700 KiB
subtask210/10
3Accepted3ms2500 KiB
4Accepted3ms2616 KiB
5Accepted3ms2968 KiB
6Accepted4ms3320 KiB
7Accepted7ms3400 KiB
subtask30/10
8Time limit exceeded3.046s24204 KiB
9Time limit exceeded3.046s32152 KiB
10Time limit exceeded3.101s51824 KiB
11Time limit exceeded3.073s91460 KiB
12Time limit exceeded3.072s209856 KiB
subtask40/20
13Runtime error326ms522772 KiB
14Runtime error296ms522536 KiB
15Runtime error282ms522292 KiB
16Runtime error244ms522264 KiB
17Runtime error236ms522004 KiB
18Runtime error246ms521960 KiB
subtask50/29
19Runtime error305ms521916 KiB
20Runtime error224ms521860 KiB
21Runtime error256ms521852 KiB
22Runtime error245ms521892 KiB
23Runtime error194ms521908 KiB
subtask60/31
24Runtime error363ms521696 KiB
25Runtime error363ms521700 KiB
26Runtime error324ms521696 KiB
27Runtime error326ms521700 KiB
28Runtime error284ms521676 KiB
29Runtime error308ms521616 KiB
30Runtime error289ms521572 KiB
31Runtime error204ms521620 KiB
32Runtime error248ms521620 KiB
33Runtime error194ms521624 KiB
34Runtime error186ms521616 KiB
35Runtime error223ms521576 KiB
36Runtime error221ms521620 KiB
37Runtime error232ms521568 KiB
38Runtime error237ms521624 KiB
39Runtime error231ms521564 KiB
40Runtime error189ms521552 KiB