Cod sursa(job #119511)

Utilizator andrei.12Andrei Parvu andrei.12 Data 1 ianuarie 2008 17:20:06
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#define lg 30005
int n, i, 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;
}