Cod sursa(job #130122)

Utilizator alexrusuRusu Alexandru alexrusu Data 31 ianuarie 2008 12:16:01
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 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;  
 }