57892023-09-30 16:05:11zsomborMajomházcpp17Hibás válasz 10/100141ms11088 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] = 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]};
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    ll l = 0, r = 1e18, 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
1Elfogadva4ms7900 KiB
2Hibás válasz9ms8176 KiB
subtask210/10
3Elfogadva4ms8472 KiB
4Elfogadva4ms8660 KiB
5Elfogadva4ms8872 KiB
6Elfogadva4ms8812 KiB
7Elfogadva4ms9068 KiB
subtask30/10
8Elfogadva6ms9160 KiB
9Hibás válasz4ms9116 KiB
10Hibás válasz6ms9372 KiB
11Hibás válasz6ms9692 KiB
12Hibás válasz4ms9968 KiB
subtask40/20
13Hibás válasz8ms9720 KiB
14Hibás válasz10ms9668 KiB
15Hibás válasz10ms9668 KiB
16Hibás válasz12ms9700 KiB
17Hibás válasz12ms9724 KiB
18Hibás válasz10ms9692 KiB
subtask50/29
19Hibás válasz57ms9948 KiB
20Hibás válasz61ms9868 KiB
21Hibás válasz68ms10000 KiB
22Hibás válasz71ms10292 KiB
23Hibás válasz72ms10236 KiB
subtask60/31
24Elfogadva71ms10416 KiB
25Elfogadva75ms10168 KiB
26Hibás válasz92ms10172 KiB
27Hibás válasz98ms10136 KiB
28Hibás válasz103ms10388 KiB
29Hibás válasz108ms10656 KiB
30Hibás válasz114ms10596 KiB
31Hibás válasz125ms10632 KiB
32Hibás válasz130ms10920 KiB
33Hibás válasz131ms10852 KiB
34Hibás válasz134ms10724 KiB
35Hibás válasz141ms10728 KiB
36Hibás válasz138ms10760 KiB
37Hibás válasz136ms11020 KiB
38Hibás válasz140ms11052 KiB
39Hibás válasz133ms11088 KiB
40Hibás válasz118ms10976 KiB