Cod sursa(job #190707)

Utilizator raduzerRadu Zernoveanu raduzer Data 23 mai 2008 21:44:42
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>   
  
int c[30003],l[30003],d[103],e[103],i,j,k,p,n;   
long long a[30003],x,y;   
long long s,m;   
  
int main()   
{   
    freopen("bilute.in","r",stdin);   
    freopen("bilute.out","w",stdout);   
    scanf("%d",&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("%d %lld\n",p,m);   
    return 0;   
}