Cod sursa(job #431038)

Utilizator eukristianCristian L. eukristian Data 31 martie 2010 16:36:48
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>

using namespace std;

int N,K,s[50001],v[50001];
void read_data();
void solve();

int main()
{
	read_data();
	solve();
	return 0;
}

void read_data()
{
	ifstream f("secv2.in");
	f >> N >> K;
	for (int i = 1 ; i <= N ; ++i)
		f >> v[i];
	f.close();
}

void solve()
{
	ofstream g("secv2.out");
	int max,first,last;
	for (int i = 1 ; i <= N ; ++i)
	{
		s[i] = s[i - 1] + v[i];
	}
	int min,current = 0;
	
	max = s[K];
	first = 1;
	last = K;
	
	min = s[1];

	for (int i = K + 1 ; i <= N ; ++i)
	{
		if (s[i - K] < min)
		{
			min = s[i - K];
			current = i - K + 1;
		}
		if (s[i] - min > max)
		{
			max = s[i] - min;
			first = current;
			if (!first)
				first++;
			last = i;
		}
	}
	g << first << " " << last << " " << max << endl;

}