Cod sursa(job #207163)

Utilizator alex23alexandru andronache alex23 Data 11 septembrie 2008 22:55:58
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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++)
            {if (a[j] <= 0)
                   {curent = curent - a[j];
                    if (curent >= b[i]) {b[i] = curent;
                                         lung[i] = i - j;
                                         }
                    }
                     else
                    j = i - k + 1;                         
             }
        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;
 }