Cod sursa(job #1733139)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 23 iulie 2016 18:31:16
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#define MaxN 6000001
#define INF 2000000000
using namespace std;

int v[MaxN]={},N,K,Max=-INF,Start,End;
deque <int> D;
int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&v[i]);
		v[i]+=v[i-1];
	}
	for(int i=K+1;i<=N;i++)
	{
		while(!D.empty()&&v[D.back()]>v[i-K])
			D.pop_back();
		D.push_back(i-K);
		if(Max<v[i]-v[D.front()])
			Max=v[i]-v[D.front()],Start=D.front()+1,End=i;
	}
	printf("%d %d %d",Start,End,Max);
	return 0;
}