Cod sursa(job #584470)

Utilizator bugyBogdan Vlad bugy Data 25 aprilie 2011 16:38:00
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#define dim 500005
using namespace std;

int A[dim],n,k,i,max=-dim,deque[dim],front,back,ii,x,j,ok;
char s[50];

int main()
{
	FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
	
fscanf(f,"%d %d",&n,&k);

for(i=1;i<=n;i++)
	{ok=1; j=0;
		
		fscanf(f,"%s",s);
		if(s[0]=='-')	{ok=-1; j=1;}
		
		x=s[j]-48; j++; 
		while(s[j]!='\0')
		{
			x*=10;
			x+=s[j]-48;
			j++;	
		}
		if(ok==-1)
			x=-x;
		
	A[i]=x;
	}


front=1;
back=0;

for(i=1;i<=n;i++)
{
	while(front <= back && A[ i ] <= A[ deque[ back ] ] )
		back--;
	
	deque[++back]=i;
	
	if(deque[ front ] == i-k) 
		front++;
	
	if(i>=k && A[ deque[ front ] ] > max )
		{
			max=A[ deque[ front ] ];
			ii=i-k+1;
		}
}
fprintf(g,"%d %d %d\n",ii,ii+k-1,max);

fclose(f);
fclose(g);
return 0;
}