Cod sursa(job #2824571)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 2 ianuarie 2022 17:55:53
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#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];
}