Cod sursa(job #130123)

Utilizator rchioreanRadu Chiorean rchiorean Data 31 ianuarie 2008 12:20:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
  #include <stdio.h>    
 #include <stdlib.h>    
 #include <string.h>    
int stack[1001];    
 int poz[1001];    
 int begin, end;    
     
    const int MAX = 1024;    
    char sir[MAX];    
      
  void add(int& v, int& pozitie)    
  {    
      while(stack[end] >= v && begin < end)    
      {    
          --end;    
      }    
         
      if(stack[end] >= v)     
      {    
          stack[end] = v;    
      }    
      else    
      {    
         stack[++end] = v;    
      }    
      poz[end] = pozitie;    
  }    
      
  int main(void)    
  {    
      FILE* fin;    
      FILE* fout;    
      fin = fopen("secventa.in", "r");    
      fout = fopen("secventa.out", "w");    
      int n, k;    
      fscanf(fin, "%d %d\n", &n, &k);    
      
      int max = -30001;    
      int start = -1;    
      begin = 0;    
      end = 0;    
      stack[0] = 300001;    
          
      int ind, x;    
      x = ind = 0;    
      
      bool neg = false;    
      int i = 0;    
      
      while(fgets(sir, MAX, fin) != NULL)    
      {    
          for(; sir[ind] != '\0'; ++ind)     
          {    
              if(sir[ind] >= '0' && sir[ind] <= '9')    
                  x = x*10+(sir[ind]-'0');    
              else    
              {    
                  if(sir[ind] == '-')    
                      neg = true;    
                  else    
                  {    
                      if(neg)    
                          x *= -1;    
      
                      add(x, i);    
              
                      if(i>=k-1)    
                      {    
                          while(i-poz[begin] > k-1)    
                              ++begin;    
                          if(stack[begin] > max)    
                          {    
                              max = stack[begin];    
                              start = i-(k-1);    
                          }    
                      }    
                      x = 0;    
                      neg = false;    
                      ++i;    
                  }    
              }    
          }    
          ind = 0;    
      }    
      fclose(fin);    
      fprintf(fout, "%d %d %d\n", start+1, start+1+k-1, max);    
      fclose(fout);    
      return 0;    
  }