Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- const int INF = 0x3f3f3f3f3f3f3f3f;
- vector<int> v, s, ss;
- void fazdp(int ini, int fim, int optini, int optfim, const vector<int> &dp_ant, vector<int> &dp)
- {
- if (ini > fim) return;
- int mid = (ini + fim) >> 1;
- int resp = INF; int opt = -1;
- for (int i = optini; i <= min(mid, optfim); i++)
- {
- int atual = dp_ant[i-1] + (ss[mid] - ss[i-1]) - i * (s[mid] - s[i-1]);
- if (atual < resp) resp = atual, opt = i;
- }
- dp[mid] = resp;
- fazdp(ini, mid-1, optini, opt, dp_ant, dp);
- fazdp(mid+1, fim, opt, optfim, dp_ant, dp);
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N, K;
- cin >> N >> K;
- v.resize(N+1); s.resize(N+1); ss.resize(N+1);
- for (int i = 1; i <= N; i++)
- {
- cin >> v[i];
- s[i] = s[i-1] + v[i];
- ss[i] = ss[i-1] + v[i]*i;
- }
- vector<int> dp(N+1, INF);
- dp[0] = 0;
- for (int i = 1; i <= K; i++)
- {
- vector<int> dp2(N+1, INF);
- fazdp(1, N, 1, N, dp, dp2);
- dp = dp2;
- }
- cout << dp[N] << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
