Cod sursa(job #73930)

Utilizator andrei.12Andrei Parvu andrei.12 Data 22 iulie 2007 16:09:47
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
int sf, pozf, lgf, s, lg, poz, i, n, v[400000], cit, semn;
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-1)
			v[i+n] = v[i];
	}
	poz = 1;
	lg = 1;
	for (i=1; i<=2*n-2; i++){
		if (lg < n){
			s += v[i];
			if (s > sf){
				sf = s;
				pozf = poz;
				lgf = lg;
			}
			if (s < 0){
				s = 0;
				poz = i+1;
				lg = 0;
			}
			lg ++;
		}
		else{
			s -= v[i-n];
			poz ++;
			s += v[i];
			if (s < 0)
				break;
			else{
				if (s > sf){
					sf = s;
					pozf = poz;
					lgf = lg;
				}
				s -= v[i-n+1];
				poz ++;
				lg --;
				if (s > sf){
					sf = s;
					pozf = poz;
					lgf = lg;
				}
			}
		}
	}
	printf("%d %d %d\n", sf, pozf, lgf); 
	fclose(stdin);
	fclose(stdout);
	return 0;
}