Cod sursa(job #742041)

Utilizator florin.uncuUncu Florin florin.uncu Data 27 aprilie 2012 22:44:19
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
// http://infoarena.ro/problema/buline

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

int main(int argc, char* argv[])
{
	long N;
	int *v, *dp, maxx, p = 0, pp = 0, i, j;
	FILE *f = fopen("buline.in", "r");
	fscanf(f, "%d", &N);
	v = (int*)malloc(N * 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;
	}
	dp[0] = maxx = v[0];
	fclose(f);

	for (i = 0; i < N * 2; ++i)
	{
		j = i < N ? i : i - N;
		if(dp[i-1] > 0) {
			dp[i] = dp[i-1] + v[j];
			if(maxx < dp[i] && i < pp + N) {
				maxx = dp[i];
				p = i;
			}
		}
		else {
			dp[i] = v[j];
			if(maxx < dp[i]) {
				maxx = dp[i];
				p = i;
			}
			pp = i;
		}
	}

	f = fopen("buline.out", "w");
	fprintf(f, "%d %d %d", maxx, pp + 1, p - pp + 1);
	fclose(f);
	return 0;
}