Cod sursa(job #370497)

Utilizator undogSavu Victor Gabriel undog Data 1 decembrie 2009 14:15:41
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <stdio.h>

int v[500000];
int s[500000];

int main(){
	freopen("secventa.in","rt",stdin);
	freopen("secventa.out","wt",stdout);
	
	int i,n,k;
	int st,sf,max=-1000000;
	
	scanf("%d%d",&n,&k);
	int front=1,back=0;
	
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	
	for(i=1;i<=n;i++){
   		while( front<=back && v[i]<v[s[back]])back--;
    		s[++back]=i;
    		if(i>=k){
    			if(v[s[front]]>max){
        			max=v[s[front]];
        			st=i-k+1;
        			sf=k;
        		}
        	}
    		if(i-s[front]+1==k)front++;
    	}
	
	printf("%d %d %d",st,sf+st-1,max);
	
	return 0;
}