Cod sursa(job #595688)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 13 iunie 2011 15:48:46
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream.h>
ifstream f("buline.in");
ofstream g("buline.out");
int n,v[400005],ic,ib,lc,lb,sb,sc,m,c;
void mare()
{
	int i,maxl=sc,ll=lc,o=ic+lc;
	sc=INT_MIN;
	for(i=ic;i<o;++i) 
		{ maxl-=v[i];
		  --ll;
		  if(maxl>sc) sc=maxl,ic=i,lc=ll;
		}
}

int main()
{
	int i;
	f>>n;
	m=n+n;
	for(i=1;i<n;++i) { f>>v[i]>>c; if(c==0) v[i]*=-1; v[n+i]=v[i]; }
	f>>v[n];
	sc=-1;
	for(i=1;i<m;++i)
		{ if(sc<0) sc=v[i], ic=i, lc=1;
			  else ++lc, sc+=v[i];
		  if(lc>n) mare();
		  if(sc>sb) sb=sc,ib=ic,lb=lc;
		}
	g<<sb<<' '<<ib<<' '<<lb<<'\n';
	f.close(); g.close();
	return 0;
}