Cod sursa(job #2847230)

Utilizator george_buzasGeorge Buzas george_buzas Data 10 februarie 2022 14:41:32
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

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

int partial_sums[50001];
deque<int> partial_sums_indexes;

int main() {
	int n, k, current_element;
	fin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		fin >> current_element;
		partial_sums[i] = partial_sums[i - 1] + current_element;
	}
	int start_pos = 0, finish_pos = 0, max_sum = -1250000001;
	partial_sums_indexes.push_back(0);
	for (int i = 1; i <= n; ++i) {
		if (partial_sums_indexes.size() && partial_sums[i] < partial_sums[partial_sums_indexes.back()]) {
			partial_sums_indexes.push_back(i);
		}
		bool is_eliminated = false;
		int last_eliminated_index;
		while (partial_sums_indexes.size() && i - partial_sums_indexes.front() >= k) {
			is_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_eliminated) {
			partial_sums_indexes.push_front(last_eliminated_index);
		}
	}
	fout << start_pos << ' ' << finish_pos << ' ' << max_sum;
	return 0;
}