Cod sursa(job #491455)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 11 octombrie 2010 13:37:48
Problema Secventa 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb

#include<deque>
#include<cstdio>
#include<fstream>

using namespace std;

#define m 50001

int v[m];
int n,k,ss,st,dr;
 

void read (){
	
	ifstream in ("secv2.in");
	in>>n>>k;
	for(int i=1;i<=n;++i){
		in>>v[i];
		v[i]+=v[i-1];
		}
		in.close ();
	
	}
	
	void solve (){
		
		st=1,dr=k,ss=v[k];
		deque<int> q;
		q.push_back(1);
		q.push_back(k);
		for(int i=k+1;i<=n;++i){
			if(v[i]-v[q.front()-1]>ss)
			ss=v[i]-v[q.front()-1],q.push_back(i);
			for(;(q.front()+k<q.back())&&(ss<=v[q.back()]-v[q.front()]);q.pop_front())
			ss=v[q.back()]-v[q.front()];
			}
			st=q.front(),dr=q.back();
		
		
		}

int main ()
{
	
	read ();
	solve ();
	freopen ("secv2.out","w",stdout);
	printf("%d %d %d\n",st,dr,ss);
	
	return 0;}