57882023-09-30 15:44:28zsomborMajomházcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms7844 KiB
2Hibás válasz9ms8016 KiB
subtask210/10
3Elfogadva4ms8260 KiB
4Elfogadva4ms8556 KiB
5Elfogadva4ms8512 KiB
6Elfogadva4ms8796 KiB
7Elfogadva4ms8756 KiB
subtask30/10
8Elfogadva4ms9044 KiB
9Hibás válasz6ms9308 KiB
10Hibás válasz4ms9592 KiB
11Hibás válasz4ms9552 KiB
12Hibás válasz4ms9740 KiB
subtask40/20
13Hibás válasz9ms9928 KiB
14Hibás válasz8ms10064 KiB
15Hibás válasz8ms10116 KiB
16Hibás válasz9ms10172 KiB
17Hibás válasz9ms10020 KiB
18Hibás válasz9ms10304 KiB
subtask50/29
19Hibás válasz41ms10476 KiB
20Hibás válasz43ms10892 KiB
21Hibás válasz45ms11240 KiB
22Hibás válasz46ms11576 KiB
23Hibás válasz43ms11916 KiB
subtask60/31
24Hibás válasz68ms12780 KiB
25Hibás válasz65ms13588 KiB
26Hibás válasz68ms14464 KiB
27Hibás válasz68ms15052 KiB
28Hibás válasz71ms15632 KiB
29Hibás válasz68ms16312 KiB
30Hibás válasz71ms17072 KiB
31Hibás válasz67ms17848 KiB
32Hibás válasz68ms18400 KiB
33Hibás válasz68ms18956 KiB
34Hibás válasz70ms19632 KiB
35Hibás válasz68ms20312 KiB
36Hibás válasz67ms21112 KiB
37Hibás válasz68ms21660 KiB
38Hibás válasz68ms22596 KiB
39Hibás válasz103ms23512 KiB
40Hibás válasz85ms24160 KiB