Cod sursa(job #120909)

Utilizator raduzerRadu Zernoveanu raduzer Data 7 ianuarie 2008 10:45:00
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>

int a[30010],b[30010],c[30010],l[30010],d[110],n,s,m,p;

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