Cod sursa(job #207166)

Utilizator alex23alexandru andronache alex23 Data 11 septembrie 2008 23:07:51
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define NMAX 50100


int a[NMAX], b[NMAX], lung[NMAX];
int i, j;
int n, k;
int curent, max, poz;



int main()
 {
   FILE *f;
   
   f = fopen("secv2.in" , "r");
   fscanf(f , "%d %d" , &n , &k);
   for (i = 1; i <= n; i++)
      fscanf(f , "%d" , &a[i]);
   fclose(f);
   
   b[k] = 0;
   lung[k] = k;
   for (i = 1; i <= k; i++)
      b[k] += a[i];
   max = b[k];
   poz = k;
   
   for (i = k + 1; i <= n; i++)
       {curent = b[i] = a[i] + b[i - 1];
        lung[i] = lung[i - 1] + 1;
        for (j = i - lung[i] + 1; j <= i - k; j++)
            {curent = curent - a[j];
             if (curent <= b[i]) {b[i] = curent;
                                  lung[i] = i - j;
                                  }                       
             }
        if (max < b[i]) {max = b[i];
                         poz = i;
                         }     
        }

   
   f = fopen("secv2.out" , "w");
   fprintf(f , "%d %d %d" , poz - lung[poz] + 1 , poz , max);
   fclose(f);
                                                                    
   
       
   return 0;
 }