Cod sursa(job #612202)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 6 septembrie 2011 14:45:21
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
using namespace std;
int n,a[400010],best[400010],inc[400010];
int summax,incmax,lmax;

void Citire()
{
	int i,x,c;
	ifstream fin("buline.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x>>c;
		if(c==0)
			a[i]=a[i+n]=-x;
		else
			a[i]=a[i+n]=x;
	}
	fin.close();
}

void Rezolvare()
{
	int n1=n+n,i;
	best[1]=a[1]; summax=best[1];
	inc[1]=1; incmax=1; lmax=1;
	for(i=2;i<=n1;i++)
	{
		if(i-inc[i-1]==n)
		{
			best[i-1]-=a[inc[i-1]];
			inc[i-1]++;
		}
		if(a[i]<best[i-1]+a[i])
		{
			best[i]=best[i-1]+a[i];
			inc[i]=inc[i-1];
		}
		else
		{
			best[i]=a[i];
			inc[i]=i;
		}
		if(summax<best[i])
		{
			summax=best[i];
			lmax=i-inc[i]+1;
			incmax=inc[i]; if(incmax>n) incmax-=n;
		}
		else
			if(summax==best[i])
			{
				if(inc[i]<=n && inc[i]<=incmax)
				{
					incmax=inc[i];
					if(inc[i]==incmax)
					{
						if(i-inc[i]+1<lmax)
							lmax=i-inc[i]+1;
					}
					else
						lmax=i-inc[i]+1;
				}
				else
					if(inc[i]>n && inc[i]-n<=incmax)
					{
						incmax=inc[i]-n;
						if(inc[i]-n==incmax)
						{
							if(i-inc[i]+1<lmax)
								lmax=i-inc[i]+1;
						}
						else
							lmax=i-inc[i]+1;
					}
			}
	}
}

void Afisare()
{
	ofstream fout("buline.out");
	fout<<summax<<' '<<incmax<<' '<<lmax<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}