看到这个题，心中充满了懵逼。
我们看一下样例分析。
显然，当x=1的时候，我们可以找出2*si+ai最大的那个，然后输出它。当x=n的时候，输出Σai+sn*2。
对于其他的情况呢？我们虽然不知道正解是个啥，但是我们可以进行一番玄学猜想对不对，然后打个暴力骗分对不对？所以我们接下来进行一番猜想。
看着样例分析，不难发现这道题是个贪心。既然我们在x=1的情况中求出了2*si+ai的最大值，我们要好好的利用它。在此，我们记录下取到最大值时的住户的编号maxi（后面有排序，会打乱下标）。
我们要最大的疲劳值，所以一次推销的对象的ai越大越好（在不考虑走的路的情况下）。先按照ai排序一遍。然后进行贪心。
对于2≤x≤n-1的x：
对于推销造成的疲劳度和对于走路造成的疲劳度，我们分开计算（下文中ren是推销造成的疲劳度，lu是走路造成的疲劳度）
如果编号为maxi这个住户在排序后，在当前要选取的前x个数里面，则ren=∑ai(1<=i<=x)，否则为∑ai(1<=i<=n-1).如果这前x个住户的编号（如果maxi不在x里面，就是前x-1个住户）有大于maxi的,设这个编号为u,则lu=su*2,最后ren+lu就是答案。
解释一下为什么会分前x个和前x-1个。
因为当maxi在前x里面时，我们选择的点在是前x个，我们将它们当做一个整体。
但maxi不在前x里面时，我们选择前x-1个点，把这x-1个点看做一个整体进行处理
但是数据这么大，暴力求∑ai和u,显然会TLE的对不对？
Σai就是一个前缀和可以O(n)暴力求出来。对于求u,其实u不重要，重要的是u这个住户到出口的距离。而且我们每次要找的最大距离是排完序后,区间[1,x]里面编号的最大值，并且没有修改。这个时候用线段树啊，st表什么的都可以，由于窝刚练习完线段树，就用线段树了。
这个线段树好写多了，只有建树和查询，so窝拿出之前的板子复制粘贴然后改改再次努力手写了线段树。这样就可以ac辣
代码：
#include<bits/stdc++.h>
using namespace std;
int n,sum[100009],ma[400009];
struct zh{
int bh,l,p,q;
}r[100009];
int read()
{
char ch=getchar();
int x=0;bool f=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
f?x=-x:x=x;
return x;
}
bool cmp1(zh a,zh b)
{
return a.p>b.p;
}
void build(int k,int l,int rr)
{
if(l==rr)
{
ma[k]=r[l].bh;
return ;
}
int mid=(l+rr)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,rr);
ma[k]=max(ma[k<<1],ma[k<<1|1]);
return;
}
int query(int k,int l,int rr,int x,int y)
{
if(l>=x&&rr<=y)
{
return ma[k];
}
int maxn=-2147483647;
int mid=(l+rr)>>1;
if(x<=mid)
maxn=max(maxn,query(k<<1,l,mid,x,y));
if(mid<y)
maxn=max(maxn,query(k<<1|1,mid+1,rr,x,y));
return maxn;
}
int main()
{
int maxn=0,maxi;
n=read();int m;
for(int i=1;i<=n;i++)
r[i].l=read(),r[i].bh=i;
for(int i=1;i<=n;i++)
{
r[i].p=read();
r[i].q=r[i].l*2+r[i].p;
if(r[i].q>maxn)
maxn=r[i].q,maxi=r[i].bh;//由于后面是结构体排序，所以这里记录编号
}
m=r[n].l;//排完序之后下标就是一撮魑魅魍魉了，先记录下来，求x=n的时候用的着
sort(r+1,r+1+n,cmp1);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+r[i].p;//O(n)处理前缀和
int mi;
for(int i=1;i<=n;i++)
{
if(r[i].bh==maxi)//没有什么好的方法找到编号对应的下标，只好暴力求了,mi是编号maxi在排完序后对应的下标
{
mi=i;
break;
}
}
printf("%d\n",maxn);
for(int i=2;i<n;i++)
{int ren=0,lu=r[mi].l*2;
if(mi<=i)//分情况讨论
{
ren=sum[i];
int mm=query(1,1,n,1,i);
if(mm>mi)lu=r[mm].l*2;
int ans=ren+lu;
printf("%d\n",ans);
}
else
{ ren=r[mi].p+sum[i-1];
int mm=query(1,1,n,1,i-1);
if(mm>mi)lu=r[mm].l*2;
int ans=ren+lu;
printf("%d\n",ans);
}
}
int ans=0;//单独算x=n
for(int i=1;i<=n;i++)//貌似可以直接使用前缀和（打着打着就忘了可以用前缀和）
ans+=r[i].p;
ans+=m*2;
printf("%d\n",ans);
}