52522023-04-24 10:33:25rennMajomházcpp14Futási hiba 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";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Futási hiba259ms524696 KiB
subtask210/10
3Elfogadva3ms2272 KiB
4Elfogadva3ms2620 KiB
5Elfogadva3ms2728 KiB
6Elfogadva4ms3048 KiB
7Elfogadva7ms3272 KiB
subtask30/10
8Időlimit túllépés3.101s23968 KiB
9Időlimit túllépés3.063s31856 KiB
10Időlimit túllépés3.065s51804 KiB
11Időlimit túllépés3.082s91400 KiB
12Időlimit túllépés3.085s209720 KiB
subtask40/20
13Futási hiba284ms523120 KiB
14Futási hiba261ms523096 KiB
15Futási hiba282ms523048 KiB
16Futási hiba204ms522800 KiB
17Futási hiba189ms522652 KiB
18Futási hiba187ms522692 KiB
subtask50/29
19Futási hiba266ms522696 KiB
20Futási hiba221ms522648 KiB
21Futási hiba196ms522688 KiB
22Futási hiba243ms522424 KiB
23Futási hiba188ms522404 KiB
subtask60/31
24Futási hiba372ms522180 KiB
25Futási hiba331ms522212 KiB
26Futási hiba331ms521948 KiB
27Futási hiba291ms521916 KiB
28Futási hiba287ms521912 KiB
29Futási hiba270ms521932 KiB
30Futási hiba293ms521708 KiB
31Futási hiba207ms521596 KiB
32Futási hiba195ms521588 KiB
33Futási hiba188ms521564 KiB
34Futási hiba228ms521500 KiB
35Futási hiba181ms521508 KiB
36Futási hiba180ms521520 KiB
37Futási hiba188ms521520 KiB
38Futási hiba233ms521332 KiB
39Futási hiba185ms521336 KiB
40Futási hiba233ms521344 KiB