5790 2023. 09. 30 16:28:54 zsombor Majomház cpp17 Időlimit túllépés 40/100 3.082s 10220 KiB 
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
using ll = long long;

int n, k;
vector <ll> a(1e5 + 1, 0);
vector <ll> p(1e5 + 1, 0);
vector <ll> dp(1e5 + 1, 0);
vector <ll> cnt(1e5 + 1, -1);

ll sum(int l, int r) {
    return p[r] - p[l - 1];
}

pair <ll, ll> do_dp(ll lam) {
    dp[0] = -lam;
    int last = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        for (int j = last; j < i; j++) {
            ll cur = dp[j] + lam + sum(j + 1, i) * (i - j);
            if (cur > dp[i]) break;
            dp[i] = cur;
            cnt[i] = cnt[j] + 1;
            last = j;
        }
    }
    return {cnt[n], dp[n]};
}

pair <ll, ll> do_dp2(ll lam) {
    dp[0] = -lam;
    int last = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        for (int j = 0; j < i; j++) {
            ll cur = dp[j] + lam + sum(j + 1, i) * (i - j);
            if (cur<=dp[i]){
                dp[i]=cur;
                cnt[i]=cnt[j]+1;
            }
        }
    }
    return {cnt[n], dp[n]};
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }

    /*fstream fajl;
    fajl.open("be2.txt");
    fajl >> n >> k;
    for (int i = 1; i <= n; i++) {
        fajl >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    fajl.close();*/

    ll l = 0, r = 1e18, m;
    while (r - l > 1) {
        m = (l + r) / 2;
        (do_dp2(m).first >= k ? l = m : r = m);
    }
    cout << do_dp2(l).second - k * l;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 7848 KiB
2 Elfogadva 1.937s 8012 KiB
subtask2 10/10
3 Elfogadva 4ms 8372 KiB
4 Elfogadva 4ms 8412 KiB
5 Elfogadva 4ms 8668 KiB
6 Elfogadva 4ms 8884 KiB
7 Elfogadva 4ms 9168 KiB
subtask3 10/10
8 Elfogadva 28ms 9036 KiB
9 Elfogadva 28ms 9168 KiB
10 Elfogadva 29ms 9456 KiB
11 Elfogadva 28ms 9644 KiB
12 Elfogadva 28ms 9652 KiB
subtask4 20/20
13 Elfogadva 2.115s 9780 KiB
14 Elfogadva 2.266s 9960 KiB
15 Elfogadva 2.388s 9740 KiB
16 Elfogadva 2.477s 10004 KiB
17 Elfogadva 2.493s 9948 KiB
18 Elfogadva 2.502s 10220 KiB
subtask5 0/29
19 Időlimit túllépés 3.061s 6524 KiB
20 Időlimit túllépés 3.065s 6476 KiB
21 Időlimit túllépés 3.061s 6476 KiB
22 Időlimit túllépés 3.073s 6692 KiB
23 Időlimit túllépés 3.065s 6680 KiB
subtask6 0/31
24 Időlimit túllépés 3.081s 6688 KiB
25 Időlimit túllépés 3.078s 6920 KiB
26 Időlimit túllépés 3.078s 6900 KiB
27 Időlimit túllépés 3.082s 6864 KiB
28 Időlimit túllépés 3.058s 6908 KiB
29 Időlimit túllépés 3.076s 7040 KiB
30 Időlimit túllépés 3.049s 7324 KiB
31 Időlimit túllépés 3.065s 7220 KiB
32 Időlimit túllépés 3.056s 7084 KiB
33 Időlimit túllépés 3.062s 7064 KiB
34 Időlimit túllépés 3.053s 7268 KiB
35 Időlimit túllépés 3.042s 7328 KiB
36 Időlimit túllépés 3.076s 7356 KiB
37 Időlimit túllépés 3.065s 7412 KiB
38 Időlimit túllépés 3.069s 7416 KiB
39 Időlimit túllépés 3.025s 7328 KiB
40 Időlimit túllépés 3.061s 7380 KiB