Cod sursa(job #112856)

Utilizator mithyPopovici Adrian mithy Data 8 decembrie 2007 03:03:31
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#define NMax 50005
#define INF 50000

long n, k, allneg = 1;
long a[NMax];
long max[NMax], lg[NMax];

void citire();
void pd();
void afis();

int main()
{
	citire();
	pd();
	afis();

	return 0 ;
}
void afis()
{
	long start=0, maxx=-INF, i;

	for (i=0; i<n; i++)
		if ( max[i] > maxx && lg[i] >= k )
		{
			maxx = max[i];
			start = i;
		}
	
	FILE *g = fopen( "secv2.out", "wt" );
	fprintf( g, "%d %d %d", start+1, start+lg[start], max[start] );
	fclose(g);
}
void pd()
{
	long i;

	max[n-1] = a[n-1];
	lg[n-1]  = 1;

	if ( !allneg )
	{
		for (i=n-2; i>=0; i--)
			if ( a[i] + max[i+1] > a[i] )
			{
				max[i] = a[i] + max[i+1];
				lg[i] = lg[i+1] + 1;
			}
			else
			{
				max[i] += a[i];
				lg[i] = 1;
			}
	}
	else
	{
		for (i=n-2; i>=0; i--)
			if ( a[i] + max[i+1] < a[i] )
			{
				max[i] = a[i] + max[i+1];
				lg[i] = lg[i+1] + 1;
			}
			else
			{
				max[i] += a[i];
				lg[i] = 1;
			}
	}
}
void citire()
{
	int i;
	FILE *f = fopen( "secv2.in", "rt" );
	fscanf( f, "%d %d", &n, &k );
	for (i=0; i<n; i++)
	{
		fscanf( f, "%d", &a[i] );
		if ( a[i] > 0 )
			allneg = 0;
	}
	fclose( f );
}