Cod sursa(job #2174054)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 16 martie 2018 10:34:15
Problema Bilute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<bits/stdc++.h>
#define maxN 30005
#define lsb(i) (i&(-i))
using namespace std;
int n;
class AIB
{
    long long a[maxN];
    public:

    inline void update(int pos,long long val)
    {
        for(int i=pos;i<=n;i+=lsb(i))
            a[i]+=val;
    }

    inline long long query(int pos)
    {
        long long q=0;
        for(int i=pos;i>=1;i-=lsb(i))
            q+=a[i];
        return q;
    }
}a1,a2;

pair<int,int> v[maxN];
long long sp[maxN],best=LLONG_MAX;
int pos;
int main()
{
    freopen("bilute.in","r",stdin);
    freopen("bilute.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
        a1.update(i,i*v[i].first);
        a2.update(i,v[i].first*v[i].second);
        sp[i]=sp[i-1]+v[i].first;
    }

    for(int i=1;i<=n;i++)
    {
        long long lss=sp[i-1];
        long long mr=sp[n]-sp[i];
        long long sfm=a1.query(n)-a1.query(i)-mr*i+a2.query(n)-a2.query(i);
        long long sfl=lss*i-a1.query(i-1)+a2.query(i-1);
        if((sfm+sfl)<best)
        {
            best=sfm+sfl;
            pos=i;
        }
    }

    printf("%d %lld\n",pos,best);

    return 0;
}