Cod sursa(job #239548)

Utilizator Omega91Nicodei Eduard Omega91 Data 4 ianuarie 2009 22:55:02
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>

const int NMAX = 200002;

short int v[2 * NMAX];
int N;

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


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

str_rasp rezolvare()
{
	int i, sp = 1, spmax, fpmax, s = 0, smax = v[0] - 1;
	str_rasp ret;
	for (i = 1; i < 2 * N; ++i) {
		if (i - sp == N) s -= v[sp++];
		if (smax < s) { smax = s; spmax = sp; fpmax = i - 1; }
		if (s < 0) {s = v[i]; sp = i; }
		else s += v[i];
		if (smax < s) { smax = s; spmax = sp; fpmax = i; }
	}
	ret.S = smax;
	ret.P = spmax;
	ret.L = fpmax - spmax + 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()
{
	citire();
	afisare(rezolvare());
	return 0;
}