Cod sursa(job #542826)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 27 februarie 2011 00:17:25
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#define dim 50002
using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int a[dim],best[dim];
int n,k;
int pozi,pozf;
int inceput,sfarsit;
int suma,maxim;

void citire()
{
	int i;
	f>>n>>k;
	for(i=1;i<=n;i++)
	{
		f>>a[i];
		best[i]=best[i-1]+a[i];
	}
	
}

void afisare()
{
	g<<inceput<<" "<<sfarsit<<" "<<maxim;
}

void rezolvare()
{
	int i;
	suma=best[k];
	maxim=best[k];
	inceput=pozi=1;
	sfarsit=pozf=k;
	for(i=k+1;i<=n;i++)
	{
		if(suma+a[i]<best[i]-best[i-k])
		{
			suma=best[i]-best[i-k];
			pozf=i;
			pozi=i-k+1;
		}
		else
		{
			suma=suma+a[i];
			pozf=i;
		}
	      if(suma>maxim)
		  {
			  maxim=suma;
			  inceput=pozi;
			  sfarsit=pozf;
		  }
	}
}

int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}