Cod sursa(job #20362)

Utilizator hellraizerChiperi Matei hellraizer Data 21 februarie 2007 12:15:19
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>

#define MAX 500000

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

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