Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int n, k;
- cin >> n >> k;
- vector <int> a(n);
- cin >> a;
- vector <int> pref(n), suf(n);
- pref[0] = a[0];
- for (int i = 1; i < n; ++i)
- pref[i] = pref[i - 1] + a[i];
- suf.back() = a.back();
- for (int i = n - 2; i >= 0; --i)
- suf[i] = suf[i + 1] + a[i];
- vector <int> left(n), right(n);
- left[0] = pref[0];
- for (int i = 1; i < k; ++i)
- left[i] = left[i - 1] + a[i];
- for (int i = k; i < n; ++i)
- {
- left[i] = left[i - 1];
- int val = pref[i - 1] - (i - 1 - k >= 0 ? pref[i - 1 - k] : 0);
- val += a[i];
- val -= a[i - k];
- left[i] = max(left[i], val);
- }
- right.back() = suf.back();
- for (int i = n - 2; i >= n - k; --i)
- right[i] = right[i + 1] + a[i];
- for (int i = n - k - 1; i >= 0; --i)
- {
- right[i] = right[i + 1];
- int val = suf[i + 1] - (i + 1 + k < n ? suf[i + 1 + k] : 0);
- val += a[i];
- val -= a[i + k];
- right[i] = max(right[i], val);
- }
- int ans = right[k];
- for (int i = k; i < n; ++i)
- {
- int val = max(left[i - k], i + 1 < n ? right[i + 1] : 0);
- ans = min(ans, val);
- }
- cout << ans;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement