Cod sursa(job #470247)

Utilizator darrenRares Buhai darren Data 12 iulie 2010 15:52:29
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#include<vector>
using namespace std;

class pack
{
	public:
		int c, t;
		int prod()
		{
			return c * t;
		}
};
istream& operator >> (istream& stream, pack& p)
{
	return stream >> p.c >> p.t;
}


int n, pos;
long long sum, cfin = 1LL << 60;
vector<pack> v;
vector<long long> sums1, sums2, sums3;

int main()
{
	ifstream fin("bilute.in");
	ofstream fout("bilute.out");
	fin >> n;
	v.resize(n + 2), sums1.resize(n + 2), sums2.resize(n + 2), sums3.resize(n + 2);
	
	int i;
	for (i = 1; i <= n; ++i)
	{
		fin >> v[i];
		sum += v[i].prod();
	}
	for (i = 1; i <= n; ++i)
		sums1[i] = sums1[i - 1] + v[i].c,
		sums2[i] = sums2[i - 1] + sums1[i];
	for (i = n; i >= 1; --i)
		sums1[i] = sums1[i + 1] + v[i].c,
		sums3[i] = sums3[i + 1] + sums1[i];
	
	long long cact;
	for (i = 1; i <= n; ++i)
	{
		cact = sum - v[i].prod();
		cact += sums2[i - 1] + sums3[i + 1];
		if (cact < cfin)
			cfin = cact, pos = i;
	}
	
	fout << pos << ' ' <<cfin;
}