Cod sursa(job #2021535)

Utilizator mihai.alphamihai craciun mihai.alpha Data 13 septembrie 2017 21:37:31
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

FILE *fin, *fout;

#define MAXN 30002

int n;
long long l[MAXN + 1], c[MAXN + 1];
long long st[MAXN + 1], dr[MAXN + 1];
long long staj[MAXN + 1], draj[MAXN + 1];
long long Sum;

int main() {
	fin = fopen("bilute.in", "r");
	fout = fopen("bilute.out", "w");
	fscanf(fin, "%d", &n);
	for (int i = 1; i <= n; i++)
		fscanf(fin, "%lld%lld", &c[i], &l[i]), Sum += c[i] * l[i];
	for (int i = 1; i <= n; i++) {
		staj[i] = staj[i - 1] + c[i - 1];
	}
	for (int j = n; j > 0; j--) {
		draj[j] = draj[j + 1] + c[j + 1];
	}
	for (int i = 2; i <= n; i++) {
		st[i] = st[i - 1] + staj[i];
	}
	for (int i = n - 1; i >= 1; i--) {
		dr[i] = dr[i + 1] + draj[i];
	}
	long long ans = 1LL << 62;
	int Ans;
	for (int i = 1; i <= n; i++) {
		long long rez;
		rez = Sum - c[i] * l[i] + st[i] + dr[i];
		if (rez < ans) {
			ans = rez;
			Ans = i;
		}
	}
	fprintf(fout, "%d %lld", Ans, ans);
	fclose(fin);
	fclose(fout);
	return 0;
}