52142023-04-22 19:49:21sztomiMajomházcpp11Runtime error 10/1003.101s524688 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
1Accepted3ms1832 KiB
2Runtime error257ms524688 KiB
subtask210/10
3Accepted3ms2408 KiB
4Accepted3ms2392 KiB
5Accepted3ms2408 KiB
6Accepted4ms2676 KiB
7Accepted7ms2896 KiB
subtask30/10
8Time limit exceeded3.101s23632 KiB
9Time limit exceeded3.063s31716 KiB
10Time limit exceeded3.066s51668 KiB
11Time limit exceeded3.066s91364 KiB
12Time limit exceeded3.062s209860 KiB
subtask40/20
13Runtime error284ms523100 KiB
14Runtime error307ms523036 KiB
15Runtime error239ms522900 KiB
16Runtime error202ms522880 KiB
17Runtime error193ms522592 KiB
18Runtime error194ms522660 KiB
subtask50/29
19Runtime error310ms522624 KiB
20Runtime error268ms522356 KiB
21Runtime error254ms522164 KiB
22Runtime error245ms521940 KiB
23Runtime error195ms521920 KiB
subtask60/31
24Runtime error367ms521856 KiB
25Runtime error368ms521912 KiB
26Runtime error328ms521892 KiB
27Runtime error291ms521852 KiB
28Runtime error333ms521704 KiB
29Runtime error266ms521684 KiB
30Runtime error291ms521524 KiB
31Runtime error257ms521532 KiB
32Runtime error248ms521504 KiB
33Runtime error188ms521444 KiB
34Runtime error178ms521500 KiB
35Runtime error223ms521452 KiB
36Runtime error221ms521528 KiB
37Runtime error188ms521560 KiB
38Runtime error187ms521560 KiB
39Runtime error185ms521496 KiB
40Runtime error185ms521520 KiB