Cod sursa(job #185177)
Utilizator | Oprescu Radu Constantin runnaway90 | Data | 24 aprilie 2008 20:50:29 |
---|---|---|---|
Problema | Secventa 2 | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.26 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);
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;
}