Cod sursa(job #130968)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 2 februarie 2008 18:35:05
Problema Bilute Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <stdio.h>
#define N 30005

long long n,i,s1[N],s2[N],c[N],l[N],poz,min=1000000,st,dr;

int main(){
    freopen("bilute.in","r",stdin);
    freopen("bilute.out","w",stdout);
    
    scanf("%lld",&n);
    
    for (i=1;i<=n;i++)
        scanf("%lld %lld",&c[i],&l[i]);
    
    s1[0]=0;
    s2[n+1]=0;
    for (i=1;i<=n;i++)
        s1[i]=s1[i-1]+c[i];
    for (i=n;i;i--)
        s2[i]=s2[i+1]+c[i];
    
    st=0;
    for (i=2;i<=n;i++)dr+=s2[i];
    for (i=1;i<=n;i++){
        if (st+dr-l[i]*c[i]<min){min=st+dr-l[i]*c[i];poz=i;}
        st+=s1[i];
        dr-=s2[i+1];
    }
    
    for (i=1;i<=n;i++)min+=l[i]*c[i];
    
    printf("%lld %lld\n",poz,min);
    
return 0;
}