Cod sursa(job #481134)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 30 august 2010 18:40:41
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<iostream>

using namespace std;

int main()
{
	long n,x,k,sum,maxsum=-60000,prev,bst;
	fstream fin("secv2.in", fstream::in);
	fstream fout("secv2.out", fstream::out);
	pair<long, long> min;
	pair<long, long> max;
	
	fin>>n>>k;
	//cout<<n<<" "<<k<<endl;
	
	fin>>x;
	min.first=min.second=0;

	max.first=0;
	max.second=n-1;
	maxsum=sum=prev=x;
	for(int i=1; i<n; ++i)
	{
		fin>>x;
		if(sum<min.second)
		{
			min.first=i;
			min.second=sum;
			
		}
		sum+=x;
		bst=sum-min.second;

		if(bst>=maxsum && i-min.first>=k-1)
		{
			max.first=min.first;
			max.second=i;
			maxsum=bst;
		}
		prev=x;
	}
	if(k==n)
	{
		max.first=0;
		max.second=n-1;
		maxsum=sum;
	}
	
	fout<<max.first+1<<" "<<max.second+1<<" "<<maxsum<<endl;
	//cout<<endl<<max.first+1<<" "<<max.second+1<<" "<<maxsum<<endl;
	
	fin.close();
	fout.close();
	return 0;
}