Cod sursa(job #20296)

Utilizator hellraizerChiperi Matei hellraizer Data 20 februarie 2007 23:34:58
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 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,pr;
	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;
		pr=0;
		while (d[s2]>x&&s2>=s1){
			s2--;
			pr=1;
		}
		d[++s2]=x;
		p[s2]=i;
		if (pr){
			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;
			}
			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;
}