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