题解

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int N=100005;
struct line
{
int v,s;
bool operator < (line a) const
{
return v<a.v;
}
}t[N],s;
priority_queue<line> q;
int sum,n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&t[i].s);
for(int i=1;i<=n;i++) scanf("%d",&t[i].v);
s.s=s.v=0;
q.push(s);
int now=0,maxx=0;
for(int i=1;i<=n;i++)
{
int next=now;
s=q.top();
maxx=s.v;
for(int j=now+1;j<=n;j++)
{
if(t[j].v+(t[j].s-t[now].s)*2>maxx)
{
maxx=t[j].v+(t[j].s-t[now].s)*2;
next=j;
}
}
t[next].v+=(t[next].s-t[now].s)*2;
if(next!=now) q.push(t[next]);
for(int j=now+1;j<next;j++) q.push(t[j]);
s=q.top();
sum+=s.v;
printf("%d\n",sum);
q.pop();
now=next;
}
return 0;
}