5788 2023. 09. 30 15:44:28 zsombor Majomház cpp17 Hibás válasz 10/100 103ms 24160 KiB 
#include <iostream>
#include <vector>
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] = 1e12;
        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]};
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    ll l = -1, r = 1e12, m;
    while (r - l > 1) {
        m = (l + r) / 2;
        (do_dp(m).first >= k ? l = m : r = m);
    }
    cout << do_dp(l).second - k * l;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 7844 KiB
2 Hibás válasz 9ms 8016 KiB
subtask2 10/10
3 Elfogadva 4ms 8260 KiB
4 Elfogadva 4ms 8556 KiB
5 Elfogadva 4ms 8512 KiB
6 Elfogadva 4ms 8796 KiB
7 Elfogadva 4ms 8756 KiB
subtask3 0/10
8 Elfogadva 4ms 9044 KiB
9 Hibás válasz 6ms 9308 KiB
10 Hibás válasz 4ms 9592 KiB
11 Hibás válasz 4ms 9552 KiB
12 Hibás válasz 4ms 9740 KiB
subtask4 0/20
13 Hibás válasz 9ms 9928 KiB
14 Hibás válasz 8ms 10064 KiB
15 Hibás válasz 8ms 10116 KiB
16 Hibás válasz 9ms 10172 KiB
17 Hibás válasz 9ms 10020 KiB
18 Hibás válasz 9ms 10304 KiB
subtask5 0/29
19 Hibás válasz 41ms 10476 KiB
20 Hibás válasz 43ms 10892 KiB
21 Hibás válasz 45ms 11240 KiB
22 Hibás válasz 46ms 11576 KiB
23 Hibás válasz 43ms 11916 KiB
subtask6 0/31
24 Hibás válasz 68ms 12780 KiB
25 Hibás válasz 65ms 13588 KiB
26 Hibás válasz 68ms 14464 KiB
27 Hibás válasz 68ms 15052 KiB
28 Hibás válasz 71ms 15632 KiB
29 Hibás válasz 68ms 16312 KiB
30 Hibás válasz 71ms 17072 KiB
31 Hibás válasz 67ms 17848 KiB
32 Hibás válasz 68ms 18400 KiB
33 Hibás válasz 68ms 18956 KiB
34 Hibás válasz 70ms 19632 KiB
35 Hibás válasz 68ms 20312 KiB
36 Hibás válasz 67ms 21112 KiB
37 Hibás válasz 68ms 21660 KiB
38 Hibás válasz 68ms 22596 KiB
39 Hibás válasz 103ms 23512 KiB
40 Hibás válasz 85ms 24160 KiB