Cod sursa(job #190706)

Utilizator raduzerRadu Zernoveanu raduzer Data 23 mai 2008 21:39:43
Problema Bilute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>   
  
int c[30003],l[30003],d[103],e[103];   
long long 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]+=(long long)j*d[j];   
            x+=(long long)j*d[j];   
            a[k]+=(long long)j*e[j];   
            y+=(long long)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;   
}