Cod sursa(job #299091)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 6 aprilie 2009 16:22:35
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>

const int MAXN = 50000;

#define MIN(a, b) (a) < (b) ? (a) : (b)

int S[MAXN], n,k;

int main(void) 
{
    int i,j,bestSum,beg,end,min;
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    
    scanf("%d%d",&n,&k);
    for(i = 1; i <= n; i++) 
    { 
      scanf("%d",&S[i]); 
      S[i] += S[i-1];  
    }
   
    beg = 1; end = k; bestSum = S[k];
    min = S[1];
    for(i = 1; i <= n; i++)
    {
        min = MIN(min,S[i]);
        for(j = i+k; j <= n; j++)
           if(S[j]-min > bestSum) 
           {
               bestSum = S[j]-min;
               beg = i; end = j;
           }
           else if(S[j]-min == bestSum && end-beg < j-i)
           {
               bestSum = S[j]-min;
               beg = i; end = j; 
           }  
    }
    
    printf("%d %d %d\n",beg,end,bestSum);

    fclose(stdin); fclose(stdout);
    return 0;
}