Cod sursa(job #318867)

Utilizator funkydvdIancu David Traian funkydvd Data 29 mai 2009 19:26:19
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
#define N 200001
using namespace std;
ifstream f1 ("buline.in");
ofstream f2 ("buline.out");
int sum[N],v[N];
int main()
{
	int n,a,b,i, pozs, pozd, smax=-2000000,j,sc,saux,pozaux,smin,pozs2,pozd2,pozaux2;
	f1>>n;
	for (i=1; i<=n; i++) 
	{
		f1>>a>>b;
		if (b==0)
			v[i]=-a;
		else
			v[i]=a; 
		sum[i]=sum[i-1]+v[i];
	}
	pozaux=1;
	for (i=1; i<=n; i++)
	{
		sc+=v[i];
		if (sc>smax) {smax=sc; pozs=pozaux; pozd=i;}
		if (sc<0) {sc=0; pozaux=i+1;} 
	}
	smin=2000000000;
	pozs2=1;
	pozd2=1;
	pozaux2=1;
	sc=0;
	for (i=1; i<=n; i++)
	{
		sc+=v[i];
		if (sc<smin) {smin=sc; pozs2=pozaux; pozd2=i;}
		if (sc>0) {sc=0; pozaux2=i+1;}
	}
	if (sum[n]-smin>smax) {f2<<sum[n]-smin<<" "<<pozs2<<" "<<pozd2-pozs2+n;}
	else f2<<smax<<" "<<pozs<<" "<<pozd<<pozs;
		
	return 0;
}