Cod sursa(job #117381)

Utilizator tvladTataranu Vlad tvlad Data 21 decembrie 2007 12:55:46
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>

const int N = 30010;

int n;
long long s1;
long long c[N], l[N], a[N], b[N], d1[N], d1i[N], d2[N], d2i[N];

int main() {
	freopen("bilute.in","rt",stdin);
	freopen("bilute.out","wt",stdout);
	scanf("%d",&n);
	s1 = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld %lld",&c[i],&l[i]);
		s1 += (long long)c[i]*l[i];
	}
	d1[0] = d1i[0] = 0;
	for (int i = 1; i <= n; ++i) {
		d1[i] = (long long)d1[i-1] + c[i];
		d1i[i] = (long long)d1i[i-1] + c[i]*i;
	}
	d2[n+1] = d2i[n+1] = 0;
	for (int i = n; i >= 1; --i) {
		d2[i] = (long long)d2[i+1] + c[i];
		d2i[i] = (long long)d2i[i+1] + c[i]*i;
	}
	for (int i = 1; i <= n; ++i) {
		a[i] = (long long)i*d1[i] - d1i[i];
		b[i] = (long long)-i*d2[i+1] + d2i[i+1];
	}
	long long min = 0;
	int pm = -1;
	for (int i = 1; i <= n; ++i) {
		long long t = (long long)s1 - (c[i]*l[i] - a[i] - b[i]);
		if (t < min || pm == -1) {
			min = t;
			pm = i;
		}
	}
	printf("%d %lld\n",pm,min);
	return 0;
}