52522023-04-24 10:33:25rennMajomházcpp14Runtime error 10/1003.101s524696 KiB
#include <iostream>
#include <vector>
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(0);
    cin.tie(0);

    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 error259ms524696 KiB
subtask210/10
3Accepted3ms2272 KiB
4Accepted3ms2620 KiB
5Accepted3ms2728 KiB
6Accepted4ms3048 KiB
7Accepted7ms3272 KiB
subtask30/10
8Time limit exceeded3.101s23968 KiB
9Time limit exceeded3.063s31856 KiB
10Time limit exceeded3.065s51804 KiB
11Time limit exceeded3.082s91400 KiB
12Time limit exceeded3.085s209720 KiB
subtask40/20
13Runtime error284ms523120 KiB
14Runtime error261ms523096 KiB
15Runtime error282ms523048 KiB
16Runtime error204ms522800 KiB
17Runtime error189ms522652 KiB
18Runtime error187ms522692 KiB
subtask50/29
19Runtime error266ms522696 KiB
20Runtime error221ms522648 KiB
21Runtime error196ms522688 KiB
22Runtime error243ms522424 KiB
23Runtime error188ms522404 KiB
subtask60/31
24Runtime error372ms522180 KiB
25Runtime error331ms522212 KiB
26Runtime error331ms521948 KiB
27Runtime error291ms521916 KiB
28Runtime error287ms521912 KiB
29Runtime error270ms521932 KiB
30Runtime error293ms521708 KiB
31Runtime error207ms521596 KiB
32Runtime error195ms521588 KiB
33Runtime error188ms521564 KiB
34Runtime error228ms521500 KiB
35Runtime error181ms521508 KiB
36Runtime error180ms521520 KiB
37Runtime error188ms521520 KiB
38Runtime error233ms521332 KiB
39Runtime error185ms521336 KiB
40Runtime error233ms521344 KiB