52512023-04-24 10:31:41rennMajomházcpp11Runtime error 10/1003.085s524700 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 error221ms524700 KiB
subtask210/10
3Accepted3ms2540 KiB
4Accepted3ms2868 KiB
5Accepted3ms2876 KiB
6Accepted4ms3152 KiB
7Accepted7ms3360 KiB
subtask30/10
8Time limit exceeded3.059s24412 KiB
9Time limit exceeded3.055s32260 KiB
10Time limit exceeded3.085s51924 KiB
11Time limit exceeded3.069s91856 KiB
12Time limit exceeded3.081s209660 KiB
subtask40/20
13Runtime error330ms522960 KiB
14Runtime error310ms522712 KiB
15Runtime error287ms522468 KiB
16Runtime error212ms522316 KiB
17Runtime error239ms522268 KiB
18Runtime error194ms522216 KiB
subtask50/29
19Runtime error268ms522208 KiB
20Runtime error268ms521944 KiB
21Runtime error252ms521928 KiB
22Runtime error196ms521956 KiB
23Runtime error188ms521928 KiB
subtask60/31
24Runtime error368ms521976 KiB
25Runtime error330ms521760 KiB
26Runtime error324ms521704 KiB
27Runtime error286ms521652 KiB
28Runtime error289ms521572 KiB
29Runtime error266ms521600 KiB
30Runtime error245ms521572 KiB
31Runtime error211ms521564 KiB
32Runtime error252ms521528 KiB
33Runtime error193ms521496 KiB
34Runtime error229ms521492 KiB
35Runtime error178ms521524 KiB
36Runtime error221ms521552 KiB
37Runtime error187ms521540 KiB
38Runtime error190ms521540 KiB
39Runtime error189ms521524 KiB
40Runtime error185ms521496 KiB