Cod sursa(job #316471)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 19 mai 2009 20:32:25
Problema Secventa 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#define dim 50000

long long int b[dim],c[dim];
int a[dim],n,m,i,k,l,st,dr,in[dim],ind,ind2;
long long int max;
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-1;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=-2502550;
    for(i=l-1;i<=n;i++)
    if(b[i]-c[i]>max)
    {
                     max=b[i]-c[i];
                     ind=in[i];
                     ind2=i;
                     }
    if(b[ind2]-b[1]>=max)
    {
                        printf("1 %d %d\n",ind2,b[ind2]);
                        return ;
                        }
    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;
}