Cod sursa(job #416602)

Utilizator TabaraTabara Mihai Tabara Data 13 martie 2010 00:00:20
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
using namespace std;

const char* in = "secv2.in";
const char* out = "secv2.out";
const int NMAX = 50005;
const int INF = (1<<30);

int N, K;
int sum[NMAX], A[NMAX], minx, maxx;
int best[NMAX];
int begin, end;

int main ( void )
{
	freopen ( in, "r", stdin );
	freopen ( out, "w", stdout );

	scanf ( "%d%d", &N, &K );

	int i,j,okj;
	for ( i = 1; i <= N; scanf ( "%d", A+i++ ) );
	for ( i = 1; i <= N; ++i ) sum[i] = sum[i-1] + A[i];

	maxx = -INF;
	for ( i = 1; i <= N; ++i ) {
		minx = INF;
		okj = 0;
		best[i] = sum[i];
		for ( j = 1; j <= i-K; ++j ) {
			if ( minx > sum[j] ) okj = j, minx = sum[j];
		}
		if ( minx != INF ) best[i] -= minx;
		if ( maxx < best[i] ) begin = okj+1, end = i, maxx = best[i];
	}

	printf ( "%d %d %d\n", begin, end, maxx );
	return 0;
}