Cod sursa(job #516390)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 23 decembrie 2010 21:27:44
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<iostream>
#include<fstream>
#define max_N 50005

using namespace std;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

int V[max_N], Deque[max_N], Front, Back, i, K, N, U, L, S[max_N], x1, x2, minim = -2199921;
long long Sum;

int main()
{
	fin >> N >> K;
	for(i = 1; i <= N; i ++)
	{
		fin >> V[i];
		S[i] = S[i - 1] + V[i];
	}
	
	
	Front = 1, Back = 0;
	
	for(i = 1; i <= N; i ++)
	{	
		if(i - K >= 0)
			while(S[i - K] <= S[Deque[Back]] && Back >= Front) Back --;
		if(i - K >= 0)
			Deque[++Back] = i - K;
		while(S[Deque[Front]] > S[Deque[Front + 1]]  && Deque[Front] >= 1)
			Front ++;
		if(i >= K && Deque[Front] > 0)
			if(minim < S[i] - S[Deque[Front]])
			{
				minim = S[i] - S[Deque[Front]];
				x1 = Deque[Front];
				x2 = i;
			}
		
	}
	fout << x1 + 1<< " " << x2 << " " << minim;
	return 0;
}