Cod sursa(job #1049201)

Utilizator dm1sevenDan Marius dm1seven Data 7 decembrie 2013 01:01:50
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
using namespace std;

//int pb_028_seventa2()
int main()
{
	string in_file = "secv2.in";
	string out_file = "secv2.out";

	const int MAX_N = 50000;
	int N, K;
	int x[MAX_N + 1];
	int C[MAX_N + 1];

	ifstream ifs(in_file);
	ifs >> N >> K;
	for (int i = 1; i <= N; i++) ifs >> x[i];
	ifs.close();

	C[0] = 0;
	for (int i = 1; i <= N; i++) C[i] = C[i - 1] + x[i];

	int id_max_end = K, id_max_start = 0;
	int id_ik_min = 0;

	for (int i = K + 1; i <= N; i++)
	{
		int global_max = C[id_max_end] - C[id_max_start];
		if (C[i - K] < C[id_ik_min]) id_ik_min = i - K;

		if (C[i] - C[id_ik_min] > global_max) { id_max_end = i; id_max_start = id_ik_min; }
	}

	ofstream ofs(out_file);
	ofs << id_max_start + 1 << " " << id_max_end << " " << C[id_max_end] - C[id_max_start];
	ofs.close();

	return 0;
}