Pagini recente » Cod sursa (job #2988662) | Cod sursa (job #1357709) | Cod sursa (job #2527337) | Cod sursa (job #2484907) | Cod sursa (job #789771)
Cod sursa(job #789771)
#include <cstdio>
using namespace std;
#define maxn 50000
#define INF 0x3f3f3f3f
long i,n,k;
long T[maxn],S[maxn],D[maxn];
long maxim=-INF,front,back,st,dr;
int main()
{
freopen ("secv2.in","r",stdin);
freopen ("secv2.out","w",stdout);
scanf ("%d %d", &n, &k );
for ( i=1; i<=n; i++ )
{
scanf ("%d", &T[i]);
S[i]=S[i-1]+T[i];
}
back=0;
front=1;
for ( i=k; i<=n; i++ )
{
while ( S[i]> S[ D[back] ] && back>0 )
back--;
back++;
D[back]=i;
}
for ( i=1; i<=n-k+1; i++ )
{
if ( D[front] < i+k-1 )
front++;
if ( maxim < S[D[front]]-S[i-1] )
{
maxim=S[D[front]]-S[i-1];
st=i;
dr=D[front];
}
}
printf("%d %d %d\n", st, dr, maxim );
return 0;
}