3064 2023. 02. 12 08:22:29 Catt Majomház cpp17 Hibás válasz 0/100 633ms 521904 KiB 
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

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


int main() {

   InTheNameOfGod;

    int n,k;
    cin >> n >> k;

    vector<int> v(n), pref(n+1, 0);
    for(int &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(int 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 1828 KiB
2 Hibás válasz 6ms 5596 KiB
subtask2 0/10
3 Hibás válasz 3ms 2140 KiB
4 Hibás válasz 3ms 2268 KiB
5 Hibás válasz 3ms 2452 KiB
6 Hibás válasz 3ms 2668 KiB
7 Hibás válasz 3ms 3008 KiB
subtask3 0/10
8 Hibás válasz 3ms 3240 KiB
9 Hibás válasz 3ms 3360 KiB
10 Hibás válasz 3ms 3792 KiB
11 Hibás válasz 3ms 4156 KiB
12 Hibás válasz 3ms 4908 KiB
subtask4 0/20
13 Hibás válasz 4ms 5104 KiB
14 Hibás válasz 4ms 5512 KiB
15 Hibás válasz 4ms 6088 KiB
16 Hibás válasz 8ms 10892 KiB
17 Hibás válasz 14ms 20020 KiB
18 Hibás válasz 75ms 83052 KiB
subtask5 0/29
19 Hibás válasz 20ms 21784 KiB
20 Hibás válasz 48ms 37684 KiB
21 Hibás válasz 104ms 90740 KiB
22 Hibás válasz 182ms 169200 KiB
23 Hibás válasz 356ms 325792 KiB
subtask6 0/31
24 Hibás válasz 34ms 28016 KiB
25 Hibás válasz 34ms 28132 KiB
26 Hibás válasz 35ms 28244 KiB
27 Hibás válasz 37ms 34228 KiB
28 Hibás válasz 37ms 34160 KiB
29 Hibás válasz 41ms 40552 KiB
30 Hibás válasz 56ms 52972 KiB
31 Hibás válasz 136ms 103108 KiB
32 Hibás válasz 345ms 178404 KiB
33 Hibás válasz 633ms 334788 KiB
34 Futási hiba 190ms 521904 KiB
35 Futási hiba 188ms 521880 KiB
36 Futási hiba 233ms 521852 KiB
37 Futási hiba 247ms 521828 KiB
38 Futási hiba 203ms 521776 KiB
39 Futási hiba 197ms 521704 KiB
40 Futási hiba 200ms 521688 KiB