Cod sursa(job #431014)

Utilizator eukristianCristian L. eukristian Data 31 martie 2010 15:56:44
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <climits>
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 = INT_MIN,first,last;
	for (int i = 1 ; i <= N ; ++i)
	{
		s[i] = s[i - 1] + v[i];
	}
	for (int i = K ; i <= N ; ++i)
	{
		int min = INT_MAX,current = 0;
		for (int j = 1 ; j <= i - K ; ++j)
		{
			if (s[j] < min)
			{
				min = s[j];
				current = j + 1;
			}
		}
		if (s[i] - (min == INT_MAX ? 0 : min) > max)
		{
			max = s[i] - (min == INT_MAX ? 0 : min);
			first = current;
			if (!first)
				first++;
			last = i;
		}
	}
	g << first << " " << last << " " << max << endl;

}