52162023-04-22 20:04:28sztomiMajomházcpp14Runtime error 10/1003.078s524704 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
1Accepted3ms1816 KiB
2Runtime error209ms524704 KiB
subtask210/10
3Accepted3ms2400 KiB
4Accepted3ms2372 KiB
5Accepted3ms2648 KiB
6Accepted4ms2712 KiB
7Accepted7ms2852 KiB
subtask30/10
8Time limit exceeded3.075s23736 KiB
9Time limit exceeded3.075s31920 KiB
10Time limit exceeded3.058s51468 KiB
11Time limit exceeded3.066s90944 KiB
12Time limit exceeded3.078s209140 KiB
subtask40/20
13Runtime error282ms523516 KiB
14Runtime error256ms523464 KiB
15Runtime error282ms523192 KiB
16Runtime error202ms523244 KiB
17Runtime error190ms522952 KiB
18Runtime error240ms522924 KiB
subtask50/29
19Runtime error259ms522704 KiB
20Runtime error266ms522680 KiB
21Runtime error199ms522636 KiB
22Runtime error197ms522640 KiB
23Runtime error192ms522472 KiB
subtask60/31
24Runtime error363ms522264 KiB
25Runtime error317ms522284 KiB
26Runtime error363ms522000 KiB
27Runtime error331ms521796 KiB
28Runtime error326ms521864 KiB
29Runtime error310ms521852 KiB
30Runtime error247ms521584 KiB
31Runtime error256ms521584 KiB
32Runtime error250ms521544 KiB
33Runtime error239ms521572 KiB
34Runtime error231ms521604 KiB
35Runtime error181ms521588 KiB
36Runtime error221ms521568 KiB
37Runtime error232ms521604 KiB
38Runtime error192ms521588 KiB
39Runtime error189ms521560 KiB
40Runtime error234ms521508 KiB