Cod sursa(job #445081)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 22 aprilie 2010 18:42:18
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include<fstream>

using namespace std;

ifstream f("bilute.in");
ofstream g("bilute.out");

int i,j,n,c[30005],l[30005],p;
long long st[30005],dr[30005],s[30005],d[30005];

int main()
{
	f>>n;
	
	for(i=1;i<=n;++i)
	{
		f>>c[i]>>l[i];
		st[i]=st[i-1]+c[i];
		s[i]=s[i-1]+c[i-1]*l[i-1]+st[i-1];
	}
	
    long long ma=(1LL<<60);
	
	for(i=n;i>0;--i)
	{
		dr[i]=dr[i+1]+c[i];
		d[i]=d[i+1]+c[i+1]*l[i+1]+dr[i+1];
		if(s[i]+d[i]<=ma) 
		{
			ma=s[i]+d[i];
			p=i;
		}
	}
	
	g<<p<<" "<<ma<<"\n";
	
	f.close();
	g.close();
	
	return 0;
}