57012023-09-09 17:40:05TomaSajtSípálya (55 pont)cpp17Wrong answer 7/5530ms11604 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> range_maxes(const vector<ll>& v, int k) {
  int n = v.size();
  vector<ll> res(n - k + 1);
  deque<int> dq;
  for (int i = 0; i < n; i++) {
    while (!dq.empty() && i - dq.front() >= k) dq.pop_front();
    while (!dq.empty() && v[dq.back()] <= v[i]) dq.pop_back();
    dq.push_back(i);
    if (i - k + 1 >= 0) {
      res[i - k + 1] = v[dq.front()];
    }
  }
  return res;
}

int main() {
  cin.tie(0), ios::sync_with_stdio(0);

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

  vector<ll> v(n);
  for (auto& a : v) cin >> a;
  for (int i = 0; i < n; i++) v[i] += i;  // add the index, so that we now need to make flat regions instead of stairs

  vector<ll> maxes = range_maxes(v, k);  // maxes[i]: max value in the i-th K length interval

  vector<int> ps(n + 1);
  partial_sum(v.begin(), v.end(), ps.begin() + 1);

  ll best = LLONG_MAX;
  for (int i = 0; i <= n - k; i++) {
    ll sum = ps[i + k] - ps[i];  // sum of values in the i-th K length interval
    ll cost = k * maxes[i] - sum;
    best = min(best, cost);
  }
  cout << best;
}
SubtaskSumTestVerdictTimeMemory
base7/55
1Accepted0/03ms1704 KiB
2Wrong answer0/03ms1928 KiB
3Wrong answer0/23ms2036 KiB
4Wrong answer0/23ms2300 KiB
5Wrong answer0/23ms2320 KiB
6Wrong answer0/23ms2524 KiB
7Wrong answer0/33ms2720 KiB
8Accepted1/14ms3364 KiB
9Accepted1/14ms3324 KiB
10Accepted1/14ms3580 KiB
11Accepted1/14ms3608 KiB
12Accepted1/14ms3608 KiB
13Wrong answer0/14ms3884 KiB
14Wrong answer0/24ms4052 KiB
15Accepted2/24ms4060 KiB
16Wrong answer0/229ms11348 KiB
17Wrong answer0/228ms9756 KiB
18Wrong answer0/228ms9752 KiB
19Wrong answer0/328ms9088 KiB
20Wrong answer0/229ms11080 KiB
21Wrong answer0/228ms11080 KiB
22Wrong answer0/229ms11080 KiB
23Wrong answer0/229ms11340 KiB
24Wrong answer0/230ms11548 KiB
25Wrong answer0/228ms11240 KiB
26Wrong answer0/228ms11280 KiB
27Wrong answer0/228ms11372 KiB
28Wrong answer0/328ms11456 KiB
29Wrong answer0/328ms11436 KiB
30Wrong answer0/328ms11604 KiB