Cod sursa(job #542706)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 26 februarie 2011 20:33:34
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
using namespace std;
int s[50002],a[50002];
int main()
{
	int i,n,k,smax=-2000000000,lim,suma,st,dr;
	ifstream fin("secv2.in");
	fin>>n>>k;
	int inc=1,sf=k;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	fin.close();
	st=1;
	dr=k;
	lim=n+1;
	while(st<lim && dr<lim)
	{
		suma=s[dr]-s[st-1];
		if(suma>smax)
		{
			smax=suma;
			inc=st;
			sf=dr;
		}
		if(dr<n)
			dr++;
		if(a[st]<1 || dr==n)
			st++;
	}
	st=n-k+1;
	dr=n;
	while(st>=0 && dr>=0)
	{
		suma=s[dr]-s[st-1];
		if(suma>smax)
		{
			smax=suma;
			inc=st;
			sf=dr;
		}
		if(st>0)
			st--;
		if(a[dr]<1 || st==0)
			dr--;
	}
	/*lim=n-k+2;
	for(st=1;st<lim;st++)
		for(dr=st+k-1;dr<n+1;dr++)
		{
			suma=s[dr]-s[st-1];
			if(suma>smax)
			{
				smax=suma;
				inc=st;
				sf=dr;
			}
		}*/
	ofstream fout("secv2.out");
	fout<<inc<<' '<<sf<<' '<<smax<<"\n";
	fout.close();
	return 0;
}