3065 2023. 02. 12 08:24:30 Catt Majomház cpp17 Hibás válasz 0/100 685ms 522988 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Hibás válasz 7ms 5872 KiB
subtask2 0/10
3 Hibás válasz 3ms 2216 KiB
4 Hibás válasz 3ms 2428 KiB
5 Hibás válasz 3ms 2676 KiB
6 Hibás válasz 3ms 2760 KiB
7 Hibás válasz 3ms 2832 KiB
subtask3 0/10
8 Hibás válasz 3ms 2924 KiB
9 Hibás válasz 3ms 3232 KiB
10 Hibás válasz 3ms 3400 KiB
11 Hibás válasz 3ms 3752 KiB
12 Hibás válasz 4ms 4812 KiB
subtask4 0/20
13 Hibás válasz 6ms 4900 KiB
14 Hibás válasz 6ms 5296 KiB
15 Hibás válasz 6ms 5840 KiB
16 Hibás válasz 9ms 10612 KiB
17 Hibás válasz 17ms 20020 KiB
18 Hibás válasz 90ms 82812 KiB
subtask5 0/29
19 Hibás válasz 35ms 22168 KiB
20 Hibás válasz 61ms 37692 KiB
21 Hibás válasz 158ms 91140 KiB
22 Hibás válasz 256ms 169444 KiB
23 Hibás válasz 384ms 325836 KiB
subtask6 0/31
24 Elfogadva 59ms 28872 KiB
25 Hibás válasz 59ms 28804 KiB
26 Hibás válasz 59ms 28800 KiB
27 Hibás válasz 64ms 34908 KiB
28 Hibás válasz 63ms 34948 KiB
29 Hibás válasz 71ms 41136 KiB
30 Hibás válasz 94ms 53624 KiB
31 Hibás válasz 214ms 103788 KiB
32 Hibás válasz 381ms 178912 KiB
33 Hibás válasz 685ms 335264 KiB
34 Futási hiba 259ms 522988 KiB
35 Futási hiba 263ms 522956 KiB
36 Futási hiba 256ms 522936 KiB
37 Futási hiba 221ms 522696 KiB
38 Futási hiba 270ms 522676 KiB
39 Futási hiba 273ms 522648 KiB
40 Futási hiba 222ms 522620 KiB