Cod sursa(job #742072)

Utilizator florin.uncuUncu Florin florin.uncu Data 28 aprilie 2012 14:12:23
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
// http://infoarena.ro/problema/buline

#include <stdio.h>
#include <malloc.h>

int main(int argc, char* argv[])
{
	long N, i, j, k, sum, l = 0, p = 0, len = 1;
	int *v, *dp;
	FILE *f = fopen("buline.in", "r");
	fscanf(f, "%d", &N);
	v  = (int*)malloc(N * 2 * sizeof(int));
	dp = (int*)malloc(N * 2 * sizeof(int));
	int semn;
	for (i = 0; i < N; ++i)
	{
		fscanf(f, "%d %d", &v[i], &semn);
		if(semn == 0) v[i] *= -1;
		v[i+N] = v[i];
	}
	sum = dp[0] = v[0];
	fclose(f);

	for (i = 1; i < 2 * N; ++i)
	{
		if (len < N)
		{
			if(dp[i-1] > 0) {
				dp[i] = dp[i-1] + v[i];
				++len;
				if(sum < dp[i]) {
					sum = dp[i];
					p = i;
					l = len;
				}
			}
			else
			{
				dp[i] = v[i];
				len = 1;
				if(sum < dp[i]) {
					sum = dp[i];
					p = i;
					l = len;
				}
			}
		} 
		else
		{
			if (dp[i-1] - dp[i-len] > 0)
			{
				dp[i] = dp[i-1] - dp[i-len] + v[i];
				if(sum < dp[i]) {
					sum = dp[i];
					p = i;
					l = len;
				}
			}
			else
			{
				dp[i] = v[i];
				len = 1;
				if(sum < dp[i]) {
					sum = dp[i];
					p = i;
					l = len;
				}
			}
		}
	}
	
	f = fopen("buline.out", "w");
	fprintf(f, "%d %d %d", sum, p - l + 2, l);
	fclose(f);
	return 0;
}