Cod sursa(job #185180)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 24 aprilie 2008 20:56:56
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>
#define M 51000

long long a[M],sol[M],ss[M],b[M],max=-2000000000;
long inc,sf,n,k,i,j,ii;

int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);
    scanf("%ld %ld ",&n,&k);
    if (n<20000)
    {
                 for (i=1;i<=n;i++)  
                 {  
                    scanf("%lld",&a[i]);a[i]+=a[i-1];  
                 }  
                 for (i=1;i<=n-k+1;i++)  
                     for(j=i+k-1;j<=n;j++)  
                         if (a[j]-a[i-1]>max)  
                         {  
                                max=a[j]-a[i-1];  
                                inc=i;sf=j;  
                         }  
                 printf("%ld %ld %lld\n",inc,sf,max);  
    }
    else
    {
    for (i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
	sol[i]=a[i];
	sol[i]+=sol[i-1];
    }
    for (i=k;i<=n;i++)
        ss[i]=sol[i]-sol[i-k];
    
    for(i=1;i<=n;i++)
    {
                     if (a[i-1]>0)
                     {
                        a[i]+=a[i-1];b[i]=b[i-1];
                     }
                     else
                         b[i]=i;
                         
                     if (i-k>=0)
                     {
                               ii=b[i];
                               if (a[i-k]>0)
                               {
                                  ss[i]+=a[i-k];
				                  ii=b[i-k];
                               }
                               if (ss[i]>max)
                               {
                                             max=ss[i];
                                             inc=ii;sf=i;
                               }
                     }
    }
    
    printf("%ld %ld %lld\n",inc,sf,max);
    }
    return 0;
}