Cod sursa(job #318882)

Utilizator funkydvdIancu David Traian funkydvd Data 29 mai 2009 20:25:44
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream.h>
#define N 200001
//using namespace std;
ifstream f1 ("buline.in");
ofstream f2 ("buline.out");
int v[N];
long long sum;
int main()
{
	int n,a,b,i, pozs, pozd, smax=-20000,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+=v[i];
	}
	pozaux=1;
        sc=0;
	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;}
	}
       //	f2<<smax<<" "<<pozs<<" "<<pozd<<endl;
	smin=200000;
	pozs2=1;
	pozd2=1;
	pozaux2=1;
	sc=0;
	for (i=1; i<=n; i++)
	{
		sc+=v[i];
		if (sc<smin) {smin=sc; pozs2=pozaux2; pozd2=i;}
		if (sc>0) {sc=0; pozaux2=i+1;}
	}
       // f2<<smin<<" "<<pozs2<<" "<<pozd2<<endl;
	if (sum-smin>smax) {f2<<sum-smin<<" "<<pozd2+1<<" "<<n-pozd2+pozs2-1;}
	else f2<<smax<<" "<<pozs<<" "<<pozd;
		
	return 0;
}