Pagini recente » Cod sursa (job #341742) | Cod sursa (job #3041878) | Cod sursa (job #2657988) | Cod sursa (job #2352002) | Cod sursa (job #51625)
Cod sursa(job #51625)
#include <stdio.h>
using namespace std;
#define in "secv2.in"
#define out "secv2.out"
#define dim 50001
#define infinit 10000000
int A[dim], Nr[dim];
long long best[dim], spart[dim];
int N, K;
int main()
{
int is, ip;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
spart[0] = 0;
scanf("%d%d", &N, &K);
for ( int i = 1; i <= N; i++ )
scanf("%d", &A[i]), spart[i] = spart[i-1] + A[i];
Nr[0] = 0;
best[0] = 0;
for ( int i = 1; i <= N; i++ )
{
best[i] = A[i];
Nr[i] = i;
if ( best[i] <= A[i] + best[i-1] ) best[i] = A[i] + best[i-1], Nr[i] = Nr[i-1];
}
long long maxim = -infinit;
for ( int i = 1; i <= N; i++ )
{
//printf("%d %d\n", Nr[i], best[i] );
if ( maxim < best[i] && i-Nr[i]+1 >= K && Nr[i] != 0 ) maxim = best[i], ip = Nr[i], is = i;
}
if ( maxim == -infinit )
{
for ( int i = K; i <= N; i++ )
{
if ( maxim < spart[i] - spart[i-K] ) maxim = spart[i] - spart[i-K], ip = i-K+1, is = i;
}
printf("%d %d %d", ip, is, maxim);
}
else
{
printf("%d %d %d", ip, is, maxim);
}
return 0;
}