Cod sursa(job #710059)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 8 martie 2012 21:20:18
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <string>
#include <deque>
#include <cstdio>
using namespace std;

string x;
int dp[50005];
deque<int> d;


int main()
{
	int n,k,ind=0,ii=0,jj=0,maxim=-1<<30;
	freopen("secv2.in","r", stdin);
	freopen("secv2.out","w", stdout);

	scanf("%d %d\n",&n,&k);
	getline(cin,x);
	for(int i=0;i<x.size();i++)
	{
		if(isdigit(x[i]) || x[i]=='-')
		{
			int semn=1;
			if(x[i]=='-')
			{
				semn*=-1;
				i++;
			}
			int nr=0;
			while(isdigit(x[i]))
			{
				nr=nr*10+x[i]-'0';
				i++;
			}
			nr*=semn;
			dp[++ind]=dp[ind-1]+nr;
		}
	}
	for(int i=k;i<=n;i++)
	{
		while(d.size() && dp[i-k]<=dp[d.back()])
			d.pop_back();
		d.push_back(i-k);
		if(dp[i]-dp[d.front()]>maxim)
		{
			maxim=dp[i]-dp[d.front()];
			ii=i;
			jj=d.front()+1;
		}
		
	}
	printf("%d %d %d",jj,ii,maxim);
	return 0;
}