Cod sursa(job #727411)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 27 martie 2012 22:32:15
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<iostream>
#include<fstream>
#include<limits.h>
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=-INT_MAX;
	for(i=k;i<=n;i++) {
		while( (st<=dr) && (s[deque[st]]>s[i-k]) )
			dr--;
		deque[++dr]=i-k;
		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;
}