Cod sursa(job #163378)

Utilizator pandaemonAndrei Popescu pandaemon Data 22 martie 2008 01:34:55
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<iostream.h>
#define CMAX 30001

///ec: b[i]*t[i] + b[i]* |i-j|

int b[CMAX],t[CMAX];    // b - nr bile de culoarea i
int n,i;	         // t - durata lustruirii a b[i] bile de culoarea i
long long s[CMAX];       // s - suma primelor t[i] elemente
long long min,var,ind;

main()
{ freopen("bilute.in","r",stdin);
  freopen("bilute.out","w",stdout);

  scanf("%d",&n);

  for(i=1;i<=n;i++)
    {
     scanf("%d %d",&b[i],&t[i]);

     t[i]*=b[i]; s[i]=s[i-1]+b[i];

     min+=t[i]+b[i]*(i-1);

    }

  var=min-=t[1]; var+=t[1];

  for(i=2;i<=n;i++)

  {
    var+=s[i-1];
    var-=(s[n]-s[i-1]); var-=t[i];
    if(var<min) {min=var; ind=i;}
    var+=t[i];

  }


 printf("%lld %lld\n",ind,min);
}