Cod sursa(job #467877)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 1 iulie 2010 09:10:41
Problema Bilute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<cstdio>
#define in "bilute.in"
#define out "bilute.out"
#define N 30001
int n,c[N],l[N],nr[N],ss[N],sd[N];
void read()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&l[i]);
}
void init()
{
    nr[1]=c[1];
    for(int i=2;i<=n;i++)
        nr[i]=nr[i-1]+c[i];
    ss[1]=0;
    for(int i=2;i<=n;i++)
        ss[i]=ss[i-1]+nr[i-1]+l[i-1]*c[i-1];
    sd[n]=0;
    for(int i=n-1;i>=1;i--)
        sd[i]=sd[i+1]+nr[n]-nr[i]+l[i+1]*c[i+1];
}
void solve()
{
    int min=-1,poz=-1;
    for(int i=1;i<=n;i++)
        if(ss[i]+sd[i]<min || min==-1)
            min=ss[i]+sd[i], poz=i;
    printf("%d %d\n",poz,min);
}
int main()
{
    read();
    init();
    solve();
    return 0;
}