Cod sursa(job #488743)

Utilizator ChallengeMurtaza Alexandru Challenge Data 29 septembrie 2010 20:30:55
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

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

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

int best[MaxN],st[MaxN],n,v[MaxN],sol,maxsol,a;

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

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

	fout<<best[sol]<<" "<<st[sol]<<" "<<sol-st[sol]+1;
	fout.close();
	return 0;
}