52132023-04-22 19:48:45sztomiMajomházcpp11Runtime error 10/1003.101s524704 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
1Accepted3ms1828 KiB
2Runtime error214ms524704 KiB
subtask210/10
3Accepted3ms2432 KiB
4Accepted3ms2680 KiB
5Accepted3ms2972 KiB
6Accepted4ms3184 KiB
7Accepted7ms3428 KiB
subtask30/10
8Time limit exceeded3.101s24448 KiB
9Time limit exceeded3.078s32152 KiB
10Time limit exceeded3.068s51988 KiB
11Time limit exceeded3.073s91384 KiB
12Time limit exceeded3.053s209520 KiB
subtask40/20
13Runtime error284ms523288 KiB
14Runtime error305ms523012 KiB
15Runtime error282ms522824 KiB
16Runtime error203ms522788 KiB
17Runtime error194ms522800 KiB
18Runtime error240ms522768 KiB
subtask50/29
19Runtime error307ms522708 KiB
20Runtime error266ms522500 KiB
21Runtime error202ms522316 KiB
22Runtime error246ms522316 KiB
23Runtime error243ms522300 KiB
subtask60/31
24Runtime error365ms522312 KiB
25Runtime error365ms522304 KiB
26Runtime error367ms522284 KiB
27Runtime error287ms522252 KiB
28Runtime error287ms522124 KiB
29Runtime error312ms521884 KiB
30Runtime error289ms521688 KiB
31Runtime error209ms521692 KiB
32Runtime error201ms521688 KiB
33Runtime error194ms521716 KiB
34Runtime error181ms521660 KiB
35Runtime error177ms521664 KiB
36Runtime error173ms521660 KiB
37Runtime error233ms521624 KiB
38Runtime error237ms521624 KiB
39Runtime error236ms521564 KiB
40Runtime error189ms521540 KiB