Cod sursa(job #673068)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 3 februarie 2012 20:20:53
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<iostream>
#include<fstream>
using namespace std;
int s[50001],deque[50001];
int main ()
{
	int n,i,k,start,sfarsit,max,x,st,dr;
	ifstream f("secv2.in");
	ofstream g("secv2.out");
	f>>n>>k;
	for(i=1;i<=n;i++) {
		f>>x;
		s[i]=s[i-1]+x;
	}
	f.close();
	st=1;
	dr=0;
	max=-2000000000;
	for(i=k;i<=n;i++) {
		while((st<=dr)&&(s[deque[st]]>s[i-k+1]))
			dr--;
		deque[++dr]=i-k+1;
		if((s[i]-s[deque[st]])>max) {
			max=s[i]-s[deque[st]];
			start=deque[st]+1;
			sfarsit=i;
		}
	}
	g<<start<<" "<<sfarsit<<" "<<max;
	g.close();
	return 0;
}