Cod sursa(job #447039)

Utilizator freak93Adrian Budau freak93 Data 27 aprilie 2010 16:00:21
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<fstream>

using namespace std;

const char iname[]="bilute.in";
const char oname[]="bilute.out";
const int maxn=30105;

ifstream f(iname);
ofstream g(oname);

long long n,x,y,a[maxn],l[maxn],r[maxn],mint,cost,cs[maxn],cd[maxn],w,b[maxn],i;

int main()
{
	f>>n;
	for(i=1;i<=n;++i)
	{
		f>>x>>y;
		a[i]+=x;
		b[i]=y;
		cost+=y*x;
		l[i]=l[i-1]+x;
	}
	for(i=n;i;--i)
		r[i]=r[i+1]+a[i];

	for(i=1;i<=n;++i)
		cs[i]=cs[i-1]+l[i-1];
	for(i=n;i;--i)
		cd[i]=cd[i+1]+r[i+1];
	mint=(1LL<<63)-1;
	for(i=1;i<=n;++i)
	{
		cs[i]+=cd[i];
		if(cs[i]-a[i]*b[i]<mint)
			mint=cs[i]-a[i]*b[i],w=i;
	}
	g<<w<<" "<<mint+cost<<"\n";

	f.close();
	g.close();

	return 0;
}