Cod sursa(job #267225)

Utilizator ooctavTuchila Octavian ooctav Data 26 februarie 2009 22:11:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
// secventa.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
int e[500004];
char f[3500001];
int deque[500004];
int front=0,back=1;
void parsare(FILE *f1)
{
	int x=0,p=1,i;
	bool b=false;
	fgets(f,3500000,f1);
	for(i=0;f[i]!=0;i++)
		if(f[i]==' ')
		{
			e[p]=x;
			if(b)
			{
				e[p]=-e[p];
				b=false;
			}
			p++;
			x=0;
		}
		else if(f[i]==45)
			b=true;
		else
			x=x*10+f[i]-'0';
	if(!b)
		e[p]=x;
	else
		e[p]=-x;
}
int main()
{
	int n,k,i,j=0,st=1,dr=0,poz1,poz2,baz=-1000000;
	bool b=true;
	FILE *f1,*f2;
	f1=fopen("secventa.in","r");
	f2=fopen("secventa.out","w");
	fscanf(f1,"%d %d\n",&n,&k);
	parsare(f1);
	for(i=1;i<=n;i++)
	{
		while(st<=dr && e[i]<=e[deque[dr]])
			dr--;
		deque[++dr]=i;
		if(deque[st]==i-k)
			st++;
		if(i>=k)
				if(e[deque[st]]>baz)
			{
				baz=e[deque[st]];
				poz1=i-k+1;
				poz2=i;
			}
	}
	fprintf(f2,"%d %d %d\n",poz1,poz2,baz);
	fclose(f1);
	fclose(f2);
	return 0;
}