Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- typedef unsigned int UI;
- typedef vector<int> VI;
- int main() {
- ios_base::sync_with_stdio(false);
- UI n, c;
- cin >> n >> c;
- VI a(n);
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- int l2n = (int) log2(n);
- l2n++;
- vector<vector<int>> sparse_table(l2n, VI(n));
- for (int j = 0; j < n; ++j) {
- sparse_table[0][j] = a[j];
- }
- for (int i = 1; i < l2n; ++i) {
- for (int j = 0; j < n; ++j) {
- sparse_table[i][j] = min(sparse_table[i - 1][j], sparse_table[i - 1][j + (1 << (i - 1))]);
- }
- }
- LL sum = 0;
- for (int i = 0; i < n; ++i) {
- sum += a[i];
- }
- vector<long long> d(n + 1, 0);
- d[0] = 0;
- int l2c = (int) log2(c);
- l2c = min(l2c, l2n - 1);
- for (int i = c; i <= n; ++i) {
- d[i] = max(d[i - 1], d[i - c] + min(sparse_table[l2c][i - c], sparse_table[l2c][i - (1 << l2c)]));
- }
- LL answer = sum - d[n];
- cout << answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement