5251 2023. 04. 24 10:31:41 renn Majomház cpp11 Futási hiba 10/100 3.085s 524700 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";

}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Futási hiba 221ms 524700 KiB
subtask2 10/10
3 Elfogadva 3ms 2540 KiB
4 Elfogadva 3ms 2868 KiB
5 Elfogadva 3ms 2876 KiB
6 Elfogadva 4ms 3152 KiB
7 Elfogadva 7ms 3360 KiB
subtask3 0/10
8 Időlimit túllépés 3.059s 24412 KiB
9 Időlimit túllépés 3.055s 32260 KiB
10 Időlimit túllépés 3.085s 51924 KiB
11 Időlimit túllépés 3.069s 91856 KiB
12 Időlimit túllépés 3.081s 209660 KiB
subtask4 0/20
13 Futási hiba 330ms 522960 KiB
14 Futási hiba 310ms 522712 KiB
15 Futási hiba 287ms 522468 KiB
16 Futási hiba 212ms 522316 KiB
17 Futási hiba 239ms 522268 KiB
18 Futási hiba 194ms 522216 KiB
subtask5 0/29
19 Futási hiba 268ms 522208 KiB
20 Futási hiba 268ms 521944 KiB
21 Futási hiba 252ms 521928 KiB
22 Futási hiba 196ms 521956 KiB
23 Futási hiba 188ms 521928 KiB
subtask6 0/31
24 Futási hiba 368ms 521976 KiB
25 Futási hiba 330ms 521760 KiB
26 Futási hiba 324ms 521704 KiB
27 Futási hiba 286ms 521652 KiB
28 Futási hiba 289ms 521572 KiB
29 Futási hiba 266ms 521600 KiB
30 Futási hiba 245ms 521572 KiB
31 Futási hiba 211ms 521564 KiB
32 Futási hiba 252ms 521528 KiB
33 Futási hiba 193ms 521496 KiB
34 Futási hiba 229ms 521492 KiB
35 Futási hiba 178ms 521524 KiB
36 Futási hiba 221ms 521552 KiB
37 Futási hiba 187ms 521540 KiB
38 Futási hiba 190ms 521540 KiB
39 Futási hiba 189ms 521524 KiB
40 Futási hiba 185ms 521496 KiB