Cod sursa(job #962872)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 15 iunie 2013 20:49:13
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <cstring>
#include <deque>
FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
int n,k,a[500005],q[500005],st,dr,d1,d2,mx=-30005;
long long sol=0;
char c[4000005];
void Parse()
{ char c2;
   int i,nr=0,semn=1,pas=0; fscanf(f,"%c",&c2);
   fgets(c,4000005,f);
  //printf("%s",c);
  for(i=0;i<strlen(c);i++)
   { if (c[i]>=48 && c[i]<=57) nr=nr*10+(c[i]-'0');
     else
     {  if (c[i]=='-') semn=-1;
       if (c2>='0' && c2<='9')
       {pas++; nr*=semn;
        a[pas]=nr;
        semn=1;
        } nr=0;
     }
    c2=c[i];
    }
}
int main()
{ int i;
   fscanf(f,"%d %d",&n,&k);
    Parse();
    for(i=1;i<=n;i++)
  { while(st<=dr && a[i]<a[q[dr]]) dr--;
    dr++; q[dr]=i;
      while(q[st]<=i-k) st++;
      if (i>=k)
      { if (a[q[st]]>mx) {mx=a[q[st]]; d1=i; d2=d1-k+1;} }
  }
  fprintf(g,"%d %d %d",d2,d1,mx);
  //printf("%d %d\n",n,k);
  //for(i=1;i<=n;i++) printf("%d ",a[i]);
  return 0;
}