Pagini recente » Cod sursa (job #1249556) | Cod sursa (job #2652645) | Cod sursa (job #645892) | Cod sursa (job #2525419) | Cod sursa (job #2824571)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int N_MAX = 50000;
int n, k, v[N_MAX + 1], sp[N_MAX + 1];
deque<int> good_start_indices;
int best_start = 1, best_end;
int main() {
fin >> n >> k;
best_end = k;
for (int i = 1; i <= n; ++i) {
fin >> v[i];
sp[i] = sp[i - 1] + v[i];
if (i >= k) {
int start_index = i - k + 1;
/// adding the new beginning from the start index
while (!good_start_indices.empty()) {
if (sp[good_start_indices.back() - 1] < sp[start_index - 1]) {
break;
}
good_start_indices.pop_back();
}
good_start_indices.push_back(start_index);
if (sp[i] - sp[good_start_indices.front() - 1] > sp[best_end] - sp[best_start - 1]) {
best_start = good_start_indices.front();
best_end = i;
}
}
}
fout << best_start << ' ' << best_end << ' ' << sp[best_end] - sp[best_start - 1];
}