Cod sursa(job #119514)

Utilizator andrei.12Andrei Parvu andrei.12 Data 1 ianuarie 2008 17:23:14
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#define lg 30005
int n, i;
long long nr[lg], d[lg], r[lg], ss[lg];
long long s;
struct citire{
	int nr, c;
};
citire v[lg];
struct solutie{
	long long v, i;
};
solutie max;
int main()
{
	freopen("bilute.in", "rt", stdin);
	freopen("bilute.out", "wt", stdout);
   
	scanf("%d", &n);
   
	for (i=1; i<=n; i++)
		scanf("%d%d", &v[i].nr, &v[i].c);

  	for (i=1; i<=n; i++){
		nr[i] = nr[i-1] + v[i].nr * v[i].c;
		d[i] = d[i-1] - i * v[i].nr;
		ss[i] = ss[i-1] + v[i].nr;
	}


	for (i=n; i; i --)
		r[i] = r[i+1] + i*v[i].nr;

	max.v = -1;

  	for (i=1; i<=n; i++){
		s = 0;
		s = nr[i-1] + nr[n] - nr[i] + d[i-1] + r[i+1] + ss[i-1] * i - (ss[n]-ss[i])*i;
		if (s < max.v || max.v == -1)
			max.v = s, max.i = i;
	}

	printf("%lld %lld\n", max.i, max.v);

    fclose(stdin);
  	fclose(stdout);
    return 0;
}