Cod sursa(job #204222)

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

const int NMAX = 200002;

short int v[NMAX];
int N;

typedef 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 = 0; 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 = 0, spmax, fpmax, s = 0, smax = v[0] - 1;
	str_rasp ret;
	for (i = 0; i != 2 * N; ++i) {
		s += v[i];
		if (i - sp == N) s -= v[sp++];
		while(v[sp] < 0 && i - sp) s -= v[sp++];
		if (smax < s) { smax = s; spmax = sp; fpmax = i; }
	}
	ret.S = smax;
	ret.P = spmax + 1;
	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;
}