Cod sursa(job #549593)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 8 martie 2011 19:50:23
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
using namespace std;
int a[50005],best[50005],sum[50005],n,k,inc[50005];
int main()
{
	int i,x=1,y=1,smax=-2000000000,s;
	ifstream fin("secv2.in");
	fin>>n>>k;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	fin.close();
	best[1]=a[1];
	inc[1]=1;
	for(i=2;i<=n;i++)
	{
		if(best[i-1]+a[i]>a[i])
		{
			best[i]=best[i-1]+a[i];
			inc[i]=inc[i-1];			
		}
		else
		{
			best[i]=a[i];
			inc[i]=i;
		}
	}
	for(i=k;i<=n;i++)
	{
		s=sum[i]-sum[i-k+1]+best[i-k+1];
		if(s>smax)
		{
			smax=s;
			x=inc[i-k+1];
			y=i;
		}
	}
	ofstream fout("secv2.out");
	fout<<x<<' '<<y<<' '<<smax<<"\n";
	fout.close();
	return 0;
}