Cod sursa(job #204184)

Utilizator Omega91Nicodei Eduard Omega91 Data 22 august 2008 13:30:41
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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, spmax;
	smax = v[0] - 1;
	s = 0;
	sp = 0;
	for (i = 0; i != N; ++i) if (v[i] > smax) { smax = v[i]; spmax = fp = i; }
	if (smax > 0) {
		smax = v[0] - 1;
		for (i = 0; i != N; ++i) {
			if (s <= 0) { s = 0; sp = i; }
			s += v[i];
			if (s > smax) { smax = s; fp = i; spmax = sp; }
		}
		for (i = 0; i != sp; ++i) {
			if (s <= 0) break;
			s += v[i];
			if (s > smax) { smax = s; fp = i; }
		}
	}
	sp = spmax;
	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;
	v = new int [NMAX];
	citire(v, N);
	afisare(rezolvare(v, N));
	return 0;
}