Cod sursa(job #132459)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 5 februarie 2008 21:10:05
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
//Subsecventa de suma maxima de lungime >= L, complexitate O(n), varianta 2
#include <stdio.h>
long int n, v, s[50000], l;

int main()
{
   freopen("secv2.in","r",stdin);
   freopen("secv2.out","w",stdout);

   int i, j, min, max, p_min, p_max;

   scanf("%ld %ld", &n, &l);
   for (i = 1; i <= n; i++)
   {
      scanf("%ld",&v);
      s[i] = s[i-1] + v;
   }

   p_min = min = 0;
   max = s[l]; p_max = l;

   for (i = l + 1; i <= n; i++)
      {
	 if (s[i-l] < min)
	    min = s[i - l], p_min = i - l;

	 if (s[i] - min > max)
	 {
	    max = s[i] - min;
	    p_max = i;
	 }
      }

   printf("%d %d %d\n", max, p_min + 1, p_max);
   return 0;
}