Pagini recente » Cod sursa (job #218580) | Cod sursa (job #2481164) | Cod sursa (job #2556552) | Cod sursa (job #3130056) | Cod sursa (job #4566)
Cod sursa(job #4566)
/*
(C) Nemesis
Infoarena secventa 2
*/
#include<stdio.h>
#define MAXN 50001
int a[MAXN], kmin[MAXN], n, k, maxi, maxj;
int sum[MAXN], min[MAXN], max;
/*
void afis()
{
for(int i=1; i<=n; ++i) printf("%d) suma=%d min=%d kmin=%d\n",i,sum[i],min[i],kmin[i]);
}
*/
void solve()
{
sum[1]= a[1];
min[1]= a[1];
kmin[1]= 1;
// max= a[1];
maxi=0;
maxj=k;
max=0;
for(int i=1; i<=k; ++i) max+=a[i];
for(int i=2; i<=n; ++i) {
sum[i]= sum[i-1] + a[i];
if( i-k>0 && sum[i] - min[i-k] > max) { max=sum[i]- min[i-k]; maxi=kmin[i-k]; maxj=i; }
// else if( sum[i] -min[i-k] == max && maxj-maxi > kmin[i-k]-i) { max=sum[i]-min[i-k]; maxi=kmin[i-k];maxj=i; }
if(sum[i] > max && i>=k) { max=sum[i]; maxi=0; maxj=i; };
if( sum[i] < min[i-1]) { min[i]= sum[i]; kmin[i]=i; }
else { min[i]= min[i-1]; kmin[i]=kmin[i-1]; }
}
}
int main()
{
freopen("secv2.in","r",stdin);
scanf("%d %d",&n,&k);
for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
solve();
freopen("secv2.out","w",stdout);
//afis();
//printf("K=%d",k);
printf("%d %d %d\n",maxi+1,maxj,max);
}