Cod sursa(job #190704)

Utilizator raduzerRadu Zernoveanu raduzer Data 23 mai 2008 21:28:43
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>

int c[30003],l[30003],d[103],e[103];
int a[30003],x,y;
long long s,n,m,p,i,j,k;

int main()
{
    freopen("bilute.in","r",stdin);
    freopen("bilute.out","w",stdout);
    scanf("%lld",&n);
    for (i=1; i<=n; ++i)
    {
        scanf("%d %d",&c[i],&l[i]);
        s+=c[i]*l[i];
    }
    ++d[c[1]];
	++e[c[n]];
	x=0;
	y=0;
    for (i=2, k=n-1; i<=n; ++i, --k)
    {
		a[i]+=x;
		a[k]+=y;
        for (j=1; j<101; ++j) 
		{
			a[i]+=j*d[j];
			x+=j*d[j];
			a[k]+=j*e[j];
			y+=j*e[j];
		}
		++e[c[k]];
        ++d[c[i]];
    }
    m=(long long) 1000000000*1000000000;
    p=0;
    for (i=1; i<=n; ++i)
    {
        if (a[i]+s-c[i]*l[i]<m)
        {
            m=(long long)(a[i]+s-c[i]*l[i]);
            p=i;
        }
    }
    printf("%lld %lld\n",p,m);
    return 0;
}