Cod sursa(job #56788)

Utilizator MariusMarius Stroe Marius Data 30 aprilie 2007 14:33:52
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define MaxN 50001
int N, K, A[MaxN];
int best[MaxN], pred[MaxN], sum[MaxN];
int max_sum, start, end;


void read_data(void)
{
	FILE *fin = fopen("c:\\input.txt", "rt");
	int i;
	fscanf(fin, "%d %d ", &N, &K);
	for (i = 1; i <= N; i++)
		fscanf(fin, "%d ", A+i), sum[i] = A[i] + sum[i-1];
	fclose(fin);
}

void solve(void)
{
	int i;

	best[1] = A[1];
	pred[1] = 1;
	for (i = 2; i <= N; i++)
		if (A[i] > A[i] + best[i-1])
			best[i] = A[i], pred[i] = i;
		else
			best[i] = A[i] + best[i-1], pred[i] = pred[i-1];

	max_sum = -(1 << 31);
	for (i = K; i <= N; i++)
		if (max_sum < sum[i] - sum[i-K+1] + best[i-K+1])
			max_sum = sum[i] - sum[i-K+1] + best[i-K+1], start = pred[i-K+1], end = i;
}

void print(void)
{
	FILE *fout = fopen("c:\\output.txt", "wt");
	fprintf(fout, "%d %d %d", start, end, max_sum);
	fclose(fout);
}

int main(void)
{
	read_data();
	solve();
	print();

	return 0;
}