Cod sursa(job #204031)

Utilizator Omega91Nicodei Eduard Omega91 Data 21 august 2008 14:22:28
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

const int NMAX = 200002;

typedef struct str_rasp
{
	int S, P, L; //S = suma; P = pozitie; L = lungime
};


void citire(int *v, int &N)
{
	int i, b, t;
	FILE *f1;
	f1 = fopen("buline.in", "r");
	fscanf(f1, "%d", &N);
	for (i = 0; i != N; ++i) {
		fscanf(f1, "%d %d", &b, &t);
		v[i] = (2 * t - 1) * b;
	}
	fclose(f1);
}

str_rasp rezolvare(int *v, int N)
{
	str_rasp ret;
	int s, smax, sp, fp, i;
	smax = v[0] - 1;
	s = 0;
	sp = 0;
	for (i = 0; i != N; ++i) {
		if (s < 0 && v[i] > 0) { s = 0; sp = i; }
		s += v[i];
		if (s > smax) { smax = s; fp = i; }
	}
	for (i = 0; i != sp; ++i) {
		if (s < 0) break;
		s += v[i];
		if (s > smax) { smax = s; fp = i; }
	}
	ret.S = smax;
	ret.P = sp + 1;
	if (sp <= fp) ret.L = fp - sp + 1;
	else ret.L = N - sp + fp + 1;
	return ret;
}

void afisare(str_rasp x)
{
	FILE *f2;
	f2 = fopen("buline.out", "w");
	fprintf(f2, "%d %d %d\n", x.S, x.P, x.L);
	fclose(f2);
}

int main()
{
	int N, v[NMAX];
	citire(v, N);
	afisare(rezolvare(v, N));
	return 0;
}