Cod sursa(job #2807099)

Utilizator george_buzasGeorge Buzas george_buzas Data 23 noiembrie 2021 13:13:04
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <vector>
#include <climits>
using namespace std;

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

int main() {
	vector<int> start_indexes, end_indexes;
	int n, k, value, max_sum = INT_MIN, current_sum = 0, start_pos = 0, end_pos = 0;
	// current_sum - stores the maximum value between the current value and the sum of previously computed sum and current value 
	// max_sum - computes the maximum value between 0 and the largest value out of all current sums 
	fin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		fin >> value;
		if (value > current_sum + value) {
			start_pos = i;
			start_indexes.push_back(start_pos);
		}
		current_sum = max(current_sum + value, value);
		if (current_sum > max_sum) {
			end_pos = i;
			end_indexes.push_back(end_pos);
		}
		max_sum = max(current_sum, max_sum);
	}
	int length = start_indexes.size();
	for (int i = 0; i < length; ++i) {
		if (end_indexes[i] - start_indexes[i] + 1 >= k) {
			max_sum = end_indexes[i];
			start_pos = start_indexes[i];
			end_pos = end_indexes[i];
		}
	}
	fout << start_pos << ' ' << end_pos << ' ' << max_sum;
	return 0;
}