Cod sursa(job #2891551)
| Utilizator | Data | 18 aprilie 2022 22:56:57 | |
|---|---|---|---|
| Problema | Deque | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include <bits/stdc++.h>
using namespace std;
#define problem "secv2"
#define NMAX 50005
int v[NMAX], sum_part[NMAX];
int main()
{
freopen(problem ".in", "r", stdin);
freopen(problem ".out", "w", stdout);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &v[i]);
sum_part[i] = sum_part[i - 1] + v[i];
}
int ans = sum_part[k], start = 1, end = k;
deque<int> dq;
for (int i = 1; i <= n; ++i) {
if (dq.front() <= i - k && sum_part[i] - sum_part[dq.front()] > ans) {
ans = sum_part[i] - sum_part[dq.front()];
start = dq.front() + 1;
end = i;
}
while (!dq.empty() && sum_part[dq.back()] >= sum_part[i])
dq.pop_back();
dq.push_back(i);
}
printf("%d %d %d\n", start, end, ans);
}
