Pagini recente » Cod sursa (job #2313213) | Cod sursa (job #685552) | Cod sursa (job #1379280) | Cod sursa (job #2889350) | Cod sursa (job #2174054)
#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;
}