Cod sursa(job #430718)

Utilizator loginLogin Iustin Anca login Data 31 martie 2010 12:02:07
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
# include <fstream>
# include <iostream>
using namespace std;
int n, k, v[50003], dq[50003], p[50003], sol, x, y;

void read ()
{
	ifstream fin ("secv2.in");
	fin>>n>>k;
	for (int i=1;i<=n;i++)
		fin>>v[i];
}

void solve ()
{
	int scur=0, j=0, i, st=1, dr=1, s=0;
	dq[1]=0;
	p[1]=0;
	for(i=1;i<k;i++)
		scur+=v[i];
	for(;i<=n;i++)
	{
		scur+=v[i];
		if (scur-dq[st]>sol)
			sol=scur-dq[st], x=p[st], y=i;
		s+=v[++j];
		while (s<=dq[dr] && dr>=st)--dr;
		dq[++dr]=s;
		p[dr]=j+1;
	}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("secv2.out");
	fout<<x<<" "<<y<<" "<<sol;
	return 0;
}