Cod sursa(job #29638)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 martie 2007 18:15:49
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
/*
 *
 *
  info-arena 2.0 - Arhiva - Secventa
 *
 *
 */

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define INPUT "secventa.in"
#define OUTPUT "secventa.out"
#define INFI 2000000000

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

long n,k,pmin,min,val[60001],mintotal;
int a[500001];

inline void citire(){fscanf(fin, "%ld %ld", &n, &k);}

int main()
{
  int l=0;
  citire();
  memset(val,0,sizeof(val));
  min=INFI;
  for(long i=1;i<=k;++i)
  {
    fscanf(fin, "%d", &a[i]);
    ++val[a[i]+30000];
    if(a[i]+30000<min)
      min=a[i]+30000;
    mintotal=min;
    pmin=1;
  }
  for(long i=k+1;i<=n;++i)
  {
    fscanf(fin, "%d", &a[i]);
    --val[a[i-k]+30000];
    ++val[a[i]+30000];
    if(min==(a[i-k]+30000)&&val[a[i-k]+30000]==0)
    {
      l=1;
      for(long j=min;j<=60000&&l;++j)
        if(val[j]!=0)
        {
          min=j;
          if(mintotal<min)
          {
            pmin=i-k+1;
            mintotal=min;
          }
          l=0;
        }
    }
    else
    if(a[i]+30000<min)
    {
      min=a[i]+30000;
      if(mintotal<min)
      {
        pmin=i-k+1;
        mintotal=min;
      }
    }
  }
  fprintf(fout, "%ld %ld %ld\n", pmin, pmin+k-1,mintotal-30000);
  fclose(fin);
  fclose(fout);
  return 0;
}