Cod sursa(job #390030)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 2 februarie 2010 19:29:56
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

#define NMAX 52000
#define INF 1000000000

using namespace std;

int Sir[NMAX], N, K, SumeK[NMAX], Sum, bestSum, bestSt, bestFi, Inc, Final;

void Citire(void)
{
	ifstream fin("secv2.in");
		
	int i;
	bestSum = -INF;
		
	fin >>N >>K;
		
	for (i = 1; i <= N; i++)
		fin >>Sir[i];
		
	for (i = 1; i <= K; i++)
		SumeK[i] = SumeK[i-1] + Sir[i];
		
	if (SumeK[i] > bestSum) 
			bestSum = SumeK[i - 1], bestSt = i - K , bestFi = i - 1;
	
	for(; i <= N; i++)
	{
		SumeK[i] = SumeK[i-1] + Sir[i] - Sir[i - K];
		if (SumeK[i] > bestSum) 
			bestSum = SumeK[i], bestSt = i - K + 1, bestFi = i;
	}
	fin.close();
}

void Rezolva(void)
{
	int i, sum = -INF;
	
	for (i = 1; i <= N - K; i++)
	{
		if (sum + Sir[i] > Sir[i])
		{
			sum += Sir[i];
			Final = i;
			
		}
		else
		{
			sum = Sir[i];
			Final = Inc = i;
		}
		if (sum + SumeK[i + K] > bestSum) bestSum = sum + SumeK[i + K], bestSt = Inc, bestFi = Final + K;
	}
}

void Afiseaza()
{
	ofstream fout("secv2.out");
	
	fout <<bestSt <<' ' <<bestFi <<' ' <<bestSum;
	
	fout.close();
}

int main()
{
	Citire();
	
	Rezolva();
	
	Afiseaza();
	return 0;
}