Cod sursa(job #702862)

Utilizator ms-ninjacristescu liviu ms-ninja Data 2 martie 2012 09:42:32
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
using namespace std;
#define dim 50005
#define inf 0x3f3f3f3f
int v[dim], sum2[dim];
int main()
{
	ifstream fin("secv2.in");
	ofstream fout("secv2.out");
	int n, i, k;
	fin>>n >>k;
	
	for(i=1;i<=n;++i)
	{
		fin>>v[i];
		sum2[i]=v[i]+sum2[i-1];
	}
	
	
	int inc=1,ls=1, ld=k,s=0,maxim=sum2[k];
	
	
	for(i=1;i<=n;++i)
	{
		s+=v[i];
		if(s>maxim && (i-inc+1)>=k)
		{
			maxim=s;
			ls=inc;
			ld=i;
		}
		if(s<0)
		{
			s=0;
			if(maxim!=-inf)
				inc=i+1;
		}
			
		
	}
	
	maxim=0;
	for(i=ls;i<=ld;++i)
		maxim+=v[i];
	
	
	fout<<ls << " " <<ld <<" " <<maxim;
	
	return 0;
}