Cod sursa(job #20292)

Utilizator hellraizerChiperi Matei hellraizer Data 20 februarie 2007 23:26:26
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>

#define MAX 100000

int n,k,d[MAX],p[MAX],s1,s2,str,stp,b;

int main(){
	int x,l,bz,s;
	p[0]=0;
	d[1]=60000;
	s1=s2=1;
	FILE *fin=fopen("secventa.in","r");
	fscanf(fin,"%d %d",&n,&k);
	for (int i=1;i<=n;i++){
		fscanf(fin,"%d",&x);
		x+=30000;
		while (d[s2]>x&&s2>=s1)
			s2--;
		d[++s2]=x;
		p[s2]=i;
		s=s2;l=0;
		while ((l<k)&&s>=s1){
			l=p[s2]-p[s];
			bz=d[s+1];
			s--;
		}
		if (s1==s2){
			l=p[s2];
			bz=d[s1];
			s=-1;
		}
		else
			s1=s;
		if (l>=k)
			if (bz>b){
				b=bz;
				str=p[s+1]+l-k+1;
				stp=p[s2];
			}
	}
	fclose(fin);
	FILE *fout=fopen("secventa.out","w");
	fprintf(fout,"%d %d %d\n",str,stp,b-30000);
	fclose(fout);
	return 0;
}