Cod sursa(job #74035)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 iulie 2007 14:44:23
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
int n, v[400005], i, poz, lg, s, su, s2m, lgu, pozu, pozm, lgm , suma, s2, a, semn, cit; 
struct maxim{
	int val, pp;
};
maxim max;
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d", &n);
	for (i=1; i<=n; i++){
		scanf("%d%d", &cit, &semn);
		if (semn == 0)
			v[i] = -cit;
		else
			v[i] = cit;
		if (i < n)
			v[i+n] = v[i];
		suma += v[i];
	}
	poz = 1;
	lg = 1;
	for (i=1; i<=n; i++){
		s += v[i];
		if (s > su){
			su = s;
			pozu = poz;
			lgu = lg;
		}
		if (s < 0){
			s = 0;
			poz = i+1;
			lg = 1;
		}
		s2 = suma-a+max.val;
		if (s2 > s2m){
			s2m = s2;
			pozm = i;
			lgm = n-i+1+max.pp;
		}
		a += v[i];
		if (a > max.val){
			max.val = a;
			max.pp = i;
		}
		lg ++;
	}
	if (su > s2m)
		printf("%d %d %d\n", su, pozu, lgu);
	else
		if (s2m > su)
			printf("%d %d %d\n", s2m, pozm, lgm);
		else
			if (pozu < pozm)
				printf("%d %d %d\n", su, pozu, lgu);
			else
				if (pozu > pozm)
					printf("%d %d %d\n", s2m, pozm, lgm);
				else
					if (lgu < lgm)
						printf("%d %d %d\n", su, pozu, lgu);
					else
						printf("%d %d %d\n", s2m, pozm, lgm);
	fclose(stdin);
	fclose(stdout);
	return 0;
}