Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <deque>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e6 + 5;
- const ll INF = 1e18;
- ll v[maxn];
- ll B(int i) {
- return v[i] + i;
- }
- int main(){
- ios_base::sync_with_stdio(false);
- int n;
- ll k;
- cin >> n >> k;
- vector<ll> pref(n + 1, 0);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- for(int i = 0; i < n; i++) {
- pref[i + 1] = pref[i] + v[i];
- }
- deque<int> dq;
- ll res = INF;
- for(int i = 0; i < n; i++) {
- while(!dq.empty() and B(dq.back()) >= B(i)) {
- dq.pop_back();
- }
- dq.push_back(i);
- int p = i - k + 1;
- if(p < 0) {
- continue;
- }
- while(!dq.empty() and dq.front() < p) {
- dq.pop_front();
- }
- ll x_max = B(dq.front()) - p;
- if(x_max < k) {
- continue;
- }
- ll sum = pref[p + k] - pref[p];
- ll to_cut = sum - (k * x_max) + (k * (k - 1) / 2);
- ll t = 10LL * p + 5LL * to_cut;
- res = min(res, t);
- }
- if(res == INF){
- res = -1;
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment