57882023-09-30 15:44:28zsomborMajomházcpp17Wrong answer 10/100103ms24160 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms7844 KiB
2Wrong answer9ms8016 KiB
subtask210/10
3Accepted4ms8260 KiB
4Accepted4ms8556 KiB
5Accepted4ms8512 KiB
6Accepted4ms8796 KiB
7Accepted4ms8756 KiB
subtask30/10
8Accepted4ms9044 KiB
9Wrong answer6ms9308 KiB
10Wrong answer4ms9592 KiB
11Wrong answer4ms9552 KiB
12Wrong answer4ms9740 KiB
subtask40/20
13Wrong answer9ms9928 KiB
14Wrong answer8ms10064 KiB
15Wrong answer8ms10116 KiB
16Wrong answer9ms10172 KiB
17Wrong answer9ms10020 KiB
18Wrong answer9ms10304 KiB
subtask50/29
19Wrong answer41ms10476 KiB
20Wrong answer43ms10892 KiB
21Wrong answer45ms11240 KiB
22Wrong answer46ms11576 KiB
23Wrong answer43ms11916 KiB
subtask60/31
24Wrong answer68ms12780 KiB
25Wrong answer65ms13588 KiB
26Wrong answer68ms14464 KiB
27Wrong answer68ms15052 KiB
28Wrong answer71ms15632 KiB
29Wrong answer68ms16312 KiB
30Wrong answer71ms17072 KiB
31Wrong answer67ms17848 KiB
32Wrong answer68ms18400 KiB
33Wrong answer68ms18956 KiB
34Wrong answer70ms19632 KiB
35Wrong answer68ms20312 KiB
36Wrong answer67ms21112 KiB
37Wrong answer68ms21660 KiB
38Wrong answer68ms22596 KiB
39Wrong answer103ms23512 KiB
40Wrong answer85ms24160 KiB