Cod sursa(job #2847239)

Utilizator george_buzasGeorge Buzas george_buzas Data 10 februarie 2022 14:56:54
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <queue>
#define MIN_VALUE -1250000001
using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

int main() {
	int partial_sums[50001] = {0}, n, min_seq_length, current_element;
	fin >> n >> min_seq_length;
	for (int i = 1; i <= n; ++i) {
		fin >> current_element;
		partial_sums[i] = partial_sums[i - 1] + current_element;
	}
	deque<int> partial_sums_indexes;
	int start_pos = 0, finish_pos = 0, max_sum = MIN_VALUE;
	partial_sums_indexes.push_back(0);
	for (int i = 1; i <= n; ++i) {
		if (partial_sums[i] < partial_sums[partial_sums_indexes.back()]) {
			partial_sums_indexes.push_back(i);
		}
		bool is_index_eliminated = false;
		int last_eliminated_index;
		while (partial_sums_indexes.size() && i - partial_sums_indexes.front() >= min_seq_length) {
			is_index_eliminated = true;
			if (partial_sums[i] - partial_sums[partial_sums_indexes.front()] > max_sum) {
				max_sum = partial_sums[i] - partial_sums[partial_sums_indexes.front()];
				start_pos = partial_sums_indexes.front() + 1;
				finish_pos = i;
			}
			last_eliminated_index = partial_sums_indexes.front();
			partial_sums_indexes.pop_front();
		}
		if (is_index_eliminated) {
			partial_sums_indexes.push_front(last_eliminated_index);
		}
	}
	fout << start_pos << ' ' << finish_pos << ' ' << max_sum;
	return 0;
}