Cod sursa(job #116810)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2007 17:02:56
Problema Bilute Scor Ascuns
Compilator cpp Status done
Runda Marime 0.99 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

const int Nmax = 30005;

int N;
long long C[Nmax], L[Nmax];
long long Best;
int Ind;

void ReadData() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
		scanf("%lld %lld", C+i, L+i);
}

void Solve() {
	long long SumL = 0;
	long long LeftBalls = 0, RightBalls = 0;
	long long LeftCost = 0, RightCost = 0;

	for (int i = 0; i < N; ++i)
		SumL += C[i] * L[i];

	for (int i = 1; i < N; ++i) {
		RightBalls += C[i];
		RightCost += i * C[i];
	}

	Best = SumL - C[0]*L[0] + RightCost;
	Ind = 0;

	for (int i = 1; i < N; ++i) {
		RightCost -= RightBalls;
		RightBalls -= C[i];
		LeftBalls += C[i-1];
		LeftCost += LeftBalls;

		if (Best > LeftCost + RightCost + SumL - C[i]*L[i]) {
			Best = LeftCost + RightCost + SumL - C[i]*L[i];
			Ind = i;
		}
	}
}

void WriteData() {
	printf("%d %lld\n", Ind+1, Best);
}

int main() {
	freopen("bilute.in", "r", stdin);
	freopen("bilute.out", "w", stdout);

	ReadData();
	Solve();
	WriteData();
}