10367 | 2024. 04. 01 13:24:36 | MagyarKendeSZLG | Sípálya (55 pont) | cpp17 | Elfogadva 55/55 | 34ms | 23060 KiB |
#include <iostream>
#include <vector>
#include <deque>
#include <climits>
#include <numeric>
using namespace std;
using ll = unsigned long long;
#define speed cin.tie(0); ios::sync_with_stdio(0)
vector<ll> heightS;
int N, K;
int main() {
speed;
cin >> N >> K;
heightS.resize(N);
for (int i = 0; i < N; i++) {
cin >> heightS[i];
heightS[i] += i;
}
deque<pair<int, int>> q;
vector<ll> window_mx(N - K + 1);
for (int right = 0; right < K; right++) {
while (!q.empty() && q.back().first < heightS[right]) q.pop_back();
q.push_back({heightS[right], right});
}
window_mx[0] = q.front().first;
int p = 0;
int left = 1, right = K;
while (left < N - K + 1) {
while (!q.empty() && q.front().second < left) q.pop_front();
while (!q.empty() && q.back().first < heightS[right]) q.pop_back();
q.push_back({heightS[right], right});
left++;
right++;
window_mx[++p] = q.front().first;
}
ll result = ULLONG_MAX;
vector<ll> prefix(N);
partial_sum(heightS.begin(), heightS.end(), prefix.begin() + 1);
for (int i = 0; i <= N - K; i++) {
result = min(
result,
(window_mx[i] * K) -
(prefix[i + K] - prefix[i])
);
}
cout << result;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 55/55 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2028 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2400 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2620 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2844 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 3068 KiB | |||
7 | Elfogadva | 3/3 | 3ms | 3032 KiB | |||
8 | Elfogadva | 1/1 | 4ms | 3484 KiB | |||
9 | Elfogadva | 1/1 | 4ms | 3816 KiB | |||
10 | Elfogadva | 1/1 | 4ms | 3968 KiB | |||
11 | Elfogadva | 1/1 | 4ms | 4088 KiB | |||
12 | Elfogadva | 1/1 | 4ms | 4204 KiB | |||
13 | Elfogadva | 1/1 | 4ms | 4320 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 4392 KiB | |||
15 | Elfogadva | 2/2 | 4ms | 4460 KiB | |||
16 | Elfogadva | 2/2 | 32ms | 14184 KiB | |||
17 | Elfogadva | 2/2 | 30ms | 13692 KiB | |||
18 | Elfogadva | 2/2 | 30ms | 14484 KiB | |||
19 | Elfogadva | 3/3 | 30ms | 15000 KiB | |||
20 | Elfogadva | 2/2 | 32ms | 18060 KiB | |||
21 | Elfogadva | 2/2 | 32ms | 19148 KiB | |||
22 | Elfogadva | 2/2 | 32ms | 20088 KiB | |||
23 | Elfogadva | 2/2 | 32ms | 21068 KiB | |||
24 | Elfogadva | 2/2 | 34ms | 22048 KiB | |||
25 | Elfogadva | 2/2 | 32ms | 23060 KiB | |||
26 | Elfogadva | 2/2 | 32ms | 23052 KiB | |||
27 | Elfogadva | 2/2 | 32ms | 22928 KiB | |||
28 | Elfogadva | 3/3 | 32ms | 22820 KiB | |||
29 | Elfogadva | 3/3 | 30ms | 22784 KiB | |||
30 | Elfogadva | 3/3 | 32ms | 22752 KiB |