Cod sursa(job #65422)

Utilizator scapryConstantin Berzan scapry Data 9 iunie 2007 14:41:00
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <stdio.h>
#include <assert.h>

/*
 * I suck at naming variables.
 */

enum { maxn = 50001 };

int n, minlen;
int p[maxn];
int best_start, best_end, best;

//any length
int best_ending_at[maxn]; //value
int start_best_ending_at[maxn]; //start pos

//minlen
int sum_ending_at[maxn];

//minlen or more
int ending_at[maxn]; //value
int start_ending_at[maxn]; //start pos

//any length
void calc_best()
{
	best_ending_at[0] = p[0];
	start_best_ending_at[0] = 0;
	
	for(int end = 1; end < n; end++)
	{
		best_ending_at[end] = p[end];
		start_best_ending_at[end] = end;

		if(best_ending_at[end - 1] > 0) //longer better?
		{
			best_ending_at[end] += best_ending_at[end - 1];
			start_best_ending_at[end] = start_best_ending_at[end - 1];
		}
	}
}

void go()
{
	int end, i;

	calc_best();

	for(i = 0; i < minlen; i++)
		sum_ending_at[minlen - 1] += p[i];
	ending_at[minlen - 1] = sum_ending_at[minlen - 1];
	start_ending_at[minlen - 1] = 0;

	best = ending_at[minlen - 1];
	best_start = start_ending_at[minlen - 1];
	best_end = minlen - 1;

	for(end = minlen; end < n; end++)
	{
		sum_ending_at[end] = sum_ending_at[end - 1] - p[end - minlen] + p[end];
		ending_at[end] = sum_ending_at[end];

		int start = end - minlen + 1;

		start_ending_at[end] = start;

		if(best_ending_at[start - 1] > 0) //longer better?
		{
			ending_at[end] += best_ending_at[start - 1];
			start_ending_at[end] = start_best_ending_at[start - 1];
		}

		if(ending_at[end] > best)
		{
			best = ending_at[end];
			best_start = start_ending_at[end];
			best_end = end;
		}
	}
}

int main()
{
	int i;
	FILE *f = fopen("secv2.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d", &n, &minlen);
	for(i = 0; i < n; i++)
		fscanf(f, "%d", &p[i]);

	fclose(f);
	f = fopen("secv2.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
	fclose(f);
	return 0;
}