Cod sursa(job #488920)

Utilizator ChallengeMurtaza Alexandru Challenge Data 30 septembrie 2010 16:44:17
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

const char InFile[]="buline.in";
const char OutFile[]="buline.out";
const int MaxN=200005;

ifstream fin(InFile);
ofstream fout(OutFile);

int n,v[MaxN],best[MaxN],st[MaxN],a,sol,start,len,sum;

int main()
{
	fin>>n;
	best[0]=-1;
	st[1]=1;
	for(register int i=1;i<=n;++i)
	{
		fin>>v[i]>>a; 
		if(a==0)
		{
			v[i]=-v[i];
		}
		sum+=v[i];
		if(best[i-1]>=0)
		{
			st[i]=st[i-1];
			best[i]=best[i-1]+v[i];
		}
		else
		{
			st[i]=i;
			best[i]=v[i];
		}
	}
	fin.close();

	sol=best[1];
	start=1;
	len=1;
	for(register int i=2;i<=n;++i)
	{
		if(best[i]>sol)
		{
			sol=best[i];
			start=st[i];
			len=i-start+1;
		}
	}

	best[0]=1;
	st[1]=1;
	for(register int i=1;i<=n;++i)
	{
		if(best[i-1]<=0)
		{
			best[i]=best[i-1]+v[i];
			st[i]=st[i-1];
		}
		else
		{
			best[i]=v[i];
			st[i]=i;
		}
	}

	int min=1<<30,minind,minst;
	for(register int i=1;i<=n;++i)
	{
		if(best[i]<min)
		{
			min=best[i];
			minind=i;
		}
	}
	if(sum-min>sol)
	{
		sol=sum-min;
		start=minind+1;
		len=n-start+st[minind];
	}

	fout<<sol<<" "<<start<<" "<<len;
	fout.close();
	return 0;
}