Cod sursa(job #118689)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 27 decembrie 2007 16:25:24
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>

#define maxn 30010
#define min(a,b) (a < b ? a : b)
#define inf 100000000000LL
#define ll long long

ll sol,s;
int n,sum,rez;
int a[maxn],b[maxn];
ll c[maxn],d[maxn];

int main()
{
    freopen("bilute.in","r",stdin);
    freopen("bilute.out","w",stdout);
    
    scanf("%d ",&n);
    
    int i;
    
    sol=inf;
    
    for (i=1;i<=n;i++) scanf("%d %d ",&a[i],&b[i]);
    
    for (i=1;i<=n;i++) sum += a[i] * b[i];
    
    for (i=1;i<=n;i++)
    {
        c[i] = c[i-1] + s;
        s += a[i];
    }
    
    s=0;
    
    for (i=n;i>0;i--)
    {
        d[i] = d[i+1] + s;
        s += a[i];
    }
    
    for (i=1;i<=n;i++) 
        if (sum - a[i]*b[i] + c[i] + d[i] < sol)
        {
            sol = sum - a[i] * b[i] + c[i] + d[i];
            rez = i;
        }        
    
    printf("%d %lld\n",rez,sol);
    
    return 0;
}