Cod sursa(job #304512)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 13 aprilie 2009 13:53:02
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#define dim 50000

long long int b[dim],c[dim];
int a[dim],n,m,i,k,l,st,dr,max,in[dim],ind,ind2;

void read()
{
     scanf("%d %d",&n,&l);
     b[0]=0;
     for(i=1;i<=n;i++)
     {
                      scanf("%d",&a[i]);
                      b[i]=b[i-1]+a[i];
                  //    printf("%d ",b[i]);
                      }
                    //  printf("\n");
}
void solve()
{
    c[l]=c[l-1]=c[l+1]=50000;
    for(i=l;i<=n;i++)
    if(b[(i-l)+1]<c[i-1])
    {
                         c[i]=b[i-l+1];
                         in[i]=i-l+1;
                         }
    else
    {
        in[i]=in[i-1];
    c[i]=c[i-1];
}
    /*for(i=l;i<=n;i++)
    printf("%d ",b[i]-c[i]);
    printf("\n");
                 
    for(i=l;i<=n;i++)
    printf("%d ",in[i]);*/
    max=-250250;
    for(i=l;i<=n;i++)
    if(b[i]-c[i]>max)
    {
                     max=b[i]-c[i];
                     ind=in[i];
                     ind2=i;
                     }
    printf("%d %d %d\n",ind+1,ind2,max);
    
}
int main ()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    read();
    solve();
    return 0;
}