30652023-02-12 08:24:30CattMajomházcpp17Hibás válasz 0/100685ms522988 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;


int main() {
    int n,k;
    cin >> n >> k;

    vector<ll> v(n), pref(n+1, 0);
    for(ll &i : v) cin >> i;
    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i-1] + v[i-1];
    }

    vector<vector<ll>> dp(n, vector<ll>(k+1, INF)), prev(n, vector<ll>(k+1, 0));
    dp[0][0] = v[0];
    for(ll i = 1; i < n; i++) {
        dp[i][0] = dp[i-1][0] + pref[i+1] + (i) * v[i];
    }
    for(int i = 0; i <= k; i++) {
        dp[0][i] = v[0];
    }
    for(int j = 1; j <= k; j++) {
        for(ll i = 1; i < n; i++) {
            ll val1 = dp[i-1][j-1] + v[i];
            ll val2 = dp[i-1][j] + pref[i+1] - pref[prev[i-1][j]] + v[i] * (i- prev[i-1][j]);

            if(val1 < val2) {
                dp[i][j] = val1;
                prev[i][j] = i;
            }
            else {
                dp[i][j] = val2;
                prev[i][j] = prev[i-1][j];
            }
        }
    }

    cout << dp[n-1][k] << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Hibás válasz7ms5872 KiB
subtask20/10
3Hibás válasz3ms2216 KiB
4Hibás válasz3ms2428 KiB
5Hibás válasz3ms2676 KiB
6Hibás válasz3ms2760 KiB
7Hibás válasz3ms2832 KiB
subtask30/10
8Hibás válasz3ms2924 KiB
9Hibás válasz3ms3232 KiB
10Hibás válasz3ms3400 KiB
11Hibás válasz3ms3752 KiB
12Hibás válasz4ms4812 KiB
subtask40/20
13Hibás válasz6ms4900 KiB
14Hibás válasz6ms5296 KiB
15Hibás válasz6ms5840 KiB
16Hibás válasz9ms10612 KiB
17Hibás válasz17ms20020 KiB
18Hibás válasz90ms82812 KiB
subtask50/29
19Hibás válasz35ms22168 KiB
20Hibás válasz61ms37692 KiB
21Hibás válasz158ms91140 KiB
22Hibás válasz256ms169444 KiB
23Hibás válasz384ms325836 KiB
subtask60/31
24Elfogadva59ms28872 KiB
25Hibás válasz59ms28804 KiB
26Hibás válasz59ms28800 KiB
27Hibás válasz64ms34908 KiB
28Hibás válasz63ms34948 KiB
29Hibás válasz71ms41136 KiB
30Hibás válasz94ms53624 KiB
31Hibás válasz214ms103788 KiB
32Hibás válasz381ms178912 KiB
33Hibás válasz685ms335264 KiB
34Futási hiba259ms522988 KiB
35Futási hiba263ms522956 KiB
36Futási hiba256ms522936 KiB
37Futási hiba221ms522696 KiB
38Futási hiba270ms522676 KiB
39Futási hiba273ms522648 KiB
40Futási hiba222ms522620 KiB