5213 2023. 04. 22 19:48:45 sztomi Majomház cpp11 Futási hiba 10/100 3.101s 524704 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 1828 KiB
2 Futási hiba 214ms 524704 KiB
subtask2 10/10
3 Elfogadva 3ms 2432 KiB
4 Elfogadva 3ms 2680 KiB
5 Elfogadva 3ms 2972 KiB
6 Elfogadva 4ms 3184 KiB
7 Elfogadva 7ms 3428 KiB
subtask3 0/10
8 Időlimit túllépés 3.101s 24448 KiB
9 Időlimit túllépés 3.078s 32152 KiB
10 Időlimit túllépés 3.068s 51988 KiB
11 Időlimit túllépés 3.073s 91384 KiB
12 Időlimit túllépés 3.053s 209520 KiB
subtask4 0/20
13 Futási hiba 284ms 523288 KiB
14 Futási hiba 305ms 523012 KiB
15 Futási hiba 282ms 522824 KiB
16 Futási hiba 203ms 522788 KiB
17 Futási hiba 194ms 522800 KiB
18 Futási hiba 240ms 522768 KiB
subtask5 0/29
19 Futási hiba 307ms 522708 KiB
20 Futási hiba 266ms 522500 KiB
21 Futási hiba 202ms 522316 KiB
22 Futási hiba 246ms 522316 KiB
23 Futási hiba 243ms 522300 KiB
subtask6 0/31
24 Futási hiba 365ms 522312 KiB
25 Futási hiba 365ms 522304 KiB
26 Futási hiba 367ms 522284 KiB
27 Futási hiba 287ms 522252 KiB
28 Futási hiba 287ms 522124 KiB
29 Futási hiba 312ms 521884 KiB
30 Futási hiba 289ms 521688 KiB
31 Futási hiba 209ms 521692 KiB
32 Futási hiba 201ms 521688 KiB
33 Futási hiba 194ms 521716 KiB
34 Futási hiba 181ms 521660 KiB
35 Futási hiba 177ms 521664 KiB
36 Futási hiba 173ms 521660 KiB
37 Futási hiba 233ms 521624 KiB
38 Futási hiba 237ms 521624 KiB
39 Futási hiba 236ms 521564 KiB
40 Futási hiba 189ms 521540 KiB