Cod sursa(job #132175)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 5 februarie 2008 11:57:41
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>

const int N_MAX = 30010;

int C[N_MAX], L[N_MAX], dr[N_MAX];
int bil;
long long MIN;

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

	int N, i;
	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &C[i], &L[i]);
	}

	long long colst = 0, coldr = 0;
	long long lst = 0, ldr = 0, sumst = 0;

	for (i = 2; i <= N; i ++) {
		ldr += C[i] * L[i];
		coldr += C[i] * (i - 1);
	}

	for (i = N; i >= 1; i --) {
		dr[i] = dr[i + 1] + C[i];
	}

	MIN = coldr + ldr;
	bil = 1;

	for (i = 2; i <= N; i ++) {
		lst += C[i - 1] * L[i - 1];
		ldr -= C[i] * L[i];

		sumst += C[i - 1];

		colst += sumst;
		coldr -= dr[i];

		if (lst + colst + ldr + coldr < MIN) {
			MIN = lst + colst + ldr + coldr;
			bil = i;
		}
	}

	printf("%d %lld\n", bil, MIN);

	return 0;
}