Cod sursa(job #160171)

Utilizator ghitza_2000Stefan Gheorghe ghitza_2000 Data 14 martie 2008 20:10:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
 #include<stdio.h>     
 FILE* f= fopen("secventa.in", "rt");     
 FILE* g= fopen("secventa.out", "wt");     
 long int deque[500010],primul=1,ultimul,N,K,maxim,PozInit,PozFin,poz[500010],cnt1,cnt2;     
 char a[20],b[3500100];     
     
 int main()     
 {fgets(a,20,f);     
 for(;a[cnt1]<='9' && a[cnt1]>='0';cnt1++)     
   N=N*10+a[cnt1]-'0';     
 cnt1++;     
 for(;a[cnt1]<='9' && a[cnt1]>='0';cnt1++)     
   K=K*10+a[cnt1]-'0';     
 fgets(b,3500100,f);     
 for(long int i=1;i<=K;i++)     
     {long int aux=0,gasit=0;     
     if(b[cnt2]=='-')     
       {gasit=1;cnt2++;}     
     for(;b[cnt2]<='9' && b[cnt2]>='0';cnt2++)     
       aux=aux*10+b[cnt2]-'0';     
     if(gasit)     
       aux*=-1;     
     while(aux<deque[ultimul] && ultimul > 0)     
        ultimul--;     
     deque[++ultimul] = aux;     
     poz[ultimul] = i;     
     cnt2++;}     
 maxim=deque[primul];     
 PozInit=poz[primul];PozFin=poz[ultimul];     
 for(long int i=K+1;i<=N;i++)     
   {long int aux=0,gasit=0;     
     if(b[cnt2]=='-')     
       {gasit=1;cnt2++;}     
     for(;b[cnt2]<='9' && b[cnt2]>='0';cnt2++)     
       aux=aux*10+b[cnt2]-'0';     
     if(gasit)     
       aux*=-1;     
    if(poz[primul]<i-K+1)     
      primul++;     
     while(aux<deque[ultimul] && ultimul >= primul)     
       ultimul--;     
   deque[++ultimul] = aux;     
   poz[ultimul] = i;     
   cnt2++;     
   if(maxim<deque[primul])     
     {maxim=deque[primul];     
     PozFin=i;     
     }     
   }     
 fprintf(g,"%ld %ld %ld",PozFin-K+1,PozFin,maxim);     
 fclose(f);     
 fclose(g);     
 return 0;     
 }