52262023-04-23 07:43:00sztomiMajomházcpp11Runtime error 10/1003.098s524700 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 error254ms524700 KiB
subtask210/10
3Accepted3ms2384 KiB
4Accepted3ms2620 KiB
5Accepted3ms2708 KiB
6Accepted4ms2852 KiB
7Accepted7ms2936 KiB
subtask30/10
8Time limit exceeded3.075s24032 KiB
9Time limit exceeded3.066s32064 KiB
10Time limit exceeded3.055s52048 KiB
11Time limit exceeded3.065s91544 KiB
12Time limit exceeded3.098s209540 KiB
subtask40/20
13Runtime error330ms523352 KiB
14Runtime error303ms523320 KiB
15Runtime error280ms523076 KiB
16Runtime error241ms523064 KiB
17Runtime error236ms522776 KiB
18Runtime error246ms522600 KiB
subtask50/29
19Runtime error305ms522572 KiB
20Runtime error268ms522528 KiB
21Runtime error256ms522592 KiB
22Runtime error247ms522572 KiB
23Runtime error241ms522532 KiB
subtask60/31
24Runtime error323ms522312 KiB
25Runtime error314ms522168 KiB
26Runtime error319ms522172 KiB
27Runtime error284ms521940 KiB
28Runtime error279ms521840 KiB
29Runtime error305ms521888 KiB
30Runtime error289ms521868 KiB
31Runtime error256ms521896 KiB
32Runtime error250ms521864 KiB
33Runtime error188ms521588 KiB
34Runtime error229ms521580 KiB
35Runtime error177ms521612 KiB
36Runtime error221ms521568 KiB
37Runtime error232ms521636 KiB
38Runtime error190ms521664 KiB
39Runtime error186ms521604 KiB
40Runtime error188ms521544 KiB