Cod sursa(job #25542)

Utilizator tvladTataranu Vlad tvlad Data 4 martie 2007 12:53:47
Problema Buline Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 1.02 kb
#include <stdio.h>
const int N = 200000;
int v[N];
int s[N];
int p[N];
int l[N];

int main() {
	freopen("buline.in", "r", stdin);
	freopen("buline.out", "w", stdout);
	
	int n;
	scanf("%d",&n);
	for (int i = 0; i<n; ++i) {
		int a;
		scanf("%d %d",&v[i],&a);
		if (a == 0) v[i] = -v[i];
	}
	s[0] = v[0];
	p[0] = 0;
	l[0] = 1;
	for (int i = 1; i<n; ++i) {
		if (s[i-1] > 0) {
			s[i] = s[i-1] + v[i];
			p[i] = p[i-1];
			l[i] = l[i-1] + 1;
		} else {
			s[i] = v[i];
			p[i] = i;
			l[i] = 1;
		}
	}
	for (int i = 0; i<n; ++i) {
		int i1 = (i-1==-1) ? n-1 : i-1;
		if (s[i1] + v[i] > s[i] && i<p[i1]) {
			s[i] = s[i1] + v[i];
			p[i] = p[i1];
			l[i] = l[i1] + 1;
		} else {
			break;
		}
	}
	int pm = 0;
	for (int i = 1; i<n; ++i) {
		if (s[i] > s[pm]) {
			pm = i;
		} else
		if (s[i] == s[pm]) {
			if (p[i] < p[pm]) {
				pm = i;
			} else
			if (p[i] == p[pm]) {
				if (l[i] < p[pm]) {
					pm = i;
				}
			}
		}
	}
	printf("%d %d %d\n",s[pm],p[pm]+1,l[pm]);
	return 0;
}