Cod sursa(job #2121430)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 3 februarie 2018 17:50:56
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#define limit 200005

using namespace std;

ifstream f("buline.in");
ofstream g("buline.out");

int n, x, sum, mx, mx2, index, length, v[limit], best[limit], lg[limit], S1[limit], lg2[limit], S2[limit];

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> v[i] >> x;
		if (!x) v[i] *= -1;
	}

	best[1] = v[1];
	lg[1] = 1;

	for (int i = 2; i <= n; i++)
		if (best[i - 1] + v[i] > v[i]) {
			best[i] = best[i - 1] + v[i];
			lg[i] = lg[i - 1] + 1;
		}
		else {
			best[i] = v[i];
			lg[i] = 1;
		}

	mx = -2000000000;

	for (int i = 1; i <= n; i++)
		if (best[i] > mx) {
			mx = best[i];
			index = i - lg[i] + 1;
			length = lg[i];
		}

	mx2 = -2000000000;

	for (int i = 1; i <= n; i++) {
		sum += v[i];
		if (mx2 < sum) {
			mx2 = sum;
			lg[i] = i;
		}
		else lg[i] = lg[i - 1];
		S1[i] = mx2;
	}

	sum = 0, mx2 = -2000000000;

	for (int i = n; i >= 1; i--) {
		sum += v[i];
		if (mx2 < sum) {
			mx2 = sum;
			lg2[i] = i;
		}
		else lg2[i] = lg2[i + 1];
		S2[i] = mx2;
	}

	for (int i = 2; i <= n; i++)
		if (S2[i] + S1[i - 1] > mx) {
			mx = S2[i] + S1[i - 1];
			index = lg2[i];
			length = (n - lg2[i] + 1) + lg[i - 1];
		}

	g << mx << ' ' << index << ' ' << length;

	f.close();
	g.close();
    return 0;
}