Pagini recente » Cod sursa (job #2529095) | Cod sursa (job #3186383) | Cod sursa (job #1477385) | Cod sursa (job #2036088) | Cod sursa (job #4559)
Cod sursa(job #4559)
/*
(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=1;
for(int i=2; i<=n; ++i) {
sum[i]= sum[i-1] + a[i];
if( sum[i] - min[i-k] > max) { max=sum[i]- min[i-k]; maxi=kmin[i-k]; maxj=i; }
if(sum[i] > max) { 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);
}