Cod sursa(job #33468)

Utilizator alextheroTandrau Alexandru alexthero Data 19 martie 2007 13:58:05
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <algorithm>

#define nmax 200005

using namespace std;

int a[nmax],s[nmax],t[nmax];
int i,n,x1,y1;

int main() {
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) {
		scanf("%d%d",&x1,&y1);
		if(y1 == 1) a[i] = x1;
		else a[i] = -x1;
	}

	t[0] = -2000000000;
	for(int i = 1; i <= n; i++) {
		s[i] = s[i - 1] + a[i];
		t[i] = max(t[i - 1],s[i]);
	}

	int rez = 0,start = 0;
	for(int i = 1; i <= n; i++) {
		int crt = t[i - 1] + s[n] - s[i - 1];
		if(rez < crt) {
			rez = crt;
			start = i;
		}
	}
	int s1 = start;

	int suma = a[start];
	int l = 1;
	while(suma != rez) {
		start++;
		l++;
		if(start == n + 1) start = 1;
		suma += a[start];
	}

	printf("%d %d %d\n",rez,s1,l);

	return 0;
}