/*
20%的数据：随便搞搞
40%的数据：同上
60%的数据：枚举N次，每次枚举每一户人家，判断这一户人家是否被推销过，
找到选择哪一户人家会得到最大的疲劳值，累加到ans里即可。
注意：若选择在当前已选最靠右的一户人家（设为x）的左边的人家（设为y），
则答案只需要增加推销这户人家的疲劳值（即ans=ans+A[y]）。
而选择x右边的人家（设为z），则答案需要增加多出来的走路疲劳值和推销这户人家的疲劳值
（即ans=ans+(d[z]-d[x])*2+A[z]）。时间复杂度O(n2)
100%的数据：和60分数据差不多，
将枚举每一户人家改为用堆维护已选的最右边的那户人家（设为x）的左边推销疲劳值的最大值（
设为堆D1）和x的右边推销疲劳值加上来回走路疲劳值的最大值（设为堆D2）。
那么每次的答案就是ans=ans+max(D1[1],D2[1]-d[x]*2)。
求答案之前要判断D1[1]和D2[1]是否合法
（即D1[1]所对应的点在x左边且没选过，D2[1]所对应的点在x的右边且没选过）。
时间复杂度O(n log2 n)。
做模拟比赛的时候想了半天
想到了线段树？
然后线段树没有滑稽币不会啊
然后就果断打了个60分暴力QAQ
然后考完一看
这个堆优化不是很容易想到吗
唉果然被普及组吓坏了
都不敢想高级算法了直接交了个暴力
Orz我好害怕
说说我的理解吧
我们很容易看到
其实对于选择n个这个问题
可以贪心的
不难想到 X= i 时的最优方案一定从 X = i-1 时的最优方案的基础上再加一户宣传对象得来。
考虑 X = 1 时的选择，显然是所有住户中 Ai + 2Si 中最大的被选，
若有多个住户的 Ai + 2Si 相同，则优先选择 Si 最小的（想一想为什么）。
然后序列被划分成左右两个部分，选择左边住户获得 Ai 的贡献，
选择右边住户获得 Ai + 2(Si - T) 的贡献，T 表示当前划分界限到胡同入口的距离，
注意右边部分的贡献的大小关系相比最初并没有改变，只需要重新对左边住户的贡献进行排序。
于是可以建一个新优先队列将左边的所有住户加入，将原优先队列中被划分到左边部分的元素丢掉。
因为划分界线是一直往右移的，所以每个元素至多被加入两次，被删除两次，
说白了就是我们每次选一个最优
只有可能是两种情况
1.继续向右走扩大距离(这个情况肯定是要选择能得到最大疲劳值的点)
2.不继续向右走了(那么我们就直接在左边选一个推销疲劳值的最大的点了)
两种情况去最大就好了
考虑到范围很大
加了个堆(优先队列)优化咯
Orz就这样没了
*/
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN=100010;
int d[MAXN],a[MAXN];
int Last,Next,n,Sum,Best;
priority_queue<int> q;//堆用来维护已选的最右边的点左边的最大值

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}

void solve()
{
    Next=0;//Next用来记录下下一个最右边点的位置
    for(int k=1;k<=n;k++)
    {
        Last=Next;//已选的最右边的点
        if(!q.empty())//q非空(即不是第一次)
            Best=q.top()+d[Last]*2;//因为sum中只保存了所有选取的疲劳值而为保存走路的疲劳值
                                   //就是直接选取了左边的最优解
        else 
            Best=0;
        for(int i=Last+1;i<=n;i++)//尝试右边可不可以更新最大疲劳值
            if(a[i]+d[i]*2>Best)
            {
                Best=a[i]+d[i]*2;
                Next=i;//记录下更新的右边的店
            }
        printf("%d\n",Sum+Best);
        if(Next==Last)//如果没有更新到最右边的点
        {
            Sum+=q.top();//就直接选取堆中的点
            q.pop();//选完了出栈
        }
        else//说明选取的是右边的点
        {
            for(int i=Last+1;i<Next;i++)//更新了最右边的点那么左边的点要跟到来入栈
                q.push(a[i]);
            Sum+=a[Next];//选上了这个点
        }
    }
}

int main()
{
    init();
    solve();
    return 0;
}

相同的代码，codeVS上满分，这里10分。。。
还又WA又T。。。
求大神帮忙看看有什么问题

#include<bits/stdc++.h>
using namespace std;
int a[100100],b[100100];
bool f[100100];
int maxi,len1,len2;
struct node{
int id;
int sum;
}c[100100],d[100100];
int cmp(node x,node y){
return x.sum<y.sum;
}
void built1(int beg,int en){
len1=0;
for(int i=beg;i<=en;i++)
if (f[i]==true){
c[i-beg+1].id=i;
c[i-beg+1].sum=b[i];
len1++;
}
make_heap(c+1,c+len1+1,cmp);
}
void built2(int beg,int en){
len2=0;
for(int i=beg;i<=en;i++)
if (f[i]==true){
d[i-beg+1].id=i;
d[i-beg+1].sum=b[i]+(a[i]-a[maxi])*2;
len2++;
}
make_heap(d+1,d+len2+1,cmp);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
maxi=1;
for(int i=1;i<=n;i++){
cin>>b[i];
if(a[i]*2+b[i]>a[maxi]*2+b[maxi]) maxi=i;
}
memset(f,true,sizeof(f));
int total=a[maxi]*2+b[maxi];
cout<<total<<endl;
f[maxi]=false;
built1(1,maxi-1);
built2(maxi+1,n);
int left=1;int right=n;
for(int i=1;i<n;i++){
int p,pmax;
int q,qmax;
pmax=c[1].sum;p=c[1].id;
qmax=d[1].sum;q=d[1].id;
int xb,m;
if (pmax>qmax){
xb=p;
m=pmax;
pop_heap(c+1,c+len1+1,cmp);
len1--;
}else{
xb=q;
maxi=q;
m=qmax;
f[q]=false;
built1(left,maxi-1);
built2(maxi+1,right);
}
total+=m;
f[xb]=false;
while(f[left]==false) left++;
while(f[right]==false) right--;
cout<<total<<endl;
}
return 0;
}

#1 Accepted 2ms 384.0KiB
#2 Wrong Answer 3ms 464.0KiB
#3 Wrong Answer 3ms 384.0KiB
#4 Wrong Answer 3ms 384.0KiB
#5 Wrong Answer 13ms 500.0KiB
#6 Wrong Answer 2ms 384.0KiB
#7 Wrong Answer 59ms 1.375MiB
#8 Time Exceeded ≥1005ms ≥1.691MiB
#9 Time Exceeded ≥1003ms ≥2.621MiB
#10 Time Exceeded ≥1001ms ≥1.965MiB

测试点#salesman1.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
测试点#salesman10.in 结果:AC 内存使用量: 3692kB 时间使用量: 310ms
测试点#salesman2.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
测试点#salesman3.in 结果:AC 内存使用量: 364kB 时间使用量: 1ms
测试点#salesman4.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
测试点#salesman5.in 结果:AC 内存使用量: 364kB 时间使用量: 2ms
测试点#salesman6.in 结果:AC 内存使用量: 364kB 时间使用量: 3ms
测试点#salesman7.in 结果:AC 内存使用量: 3944kB 时间使用量: 319ms
测试点#salesman8.in 结果:AC 内存使用量: 3948kB 时间使用量: 299ms
测试点#salesman9.in 结果:AC 内存使用量: 3692kB 时间使用量: 299ms

/*
20%的数据：随便搞搞
40%的数据：同上
60%的数据：枚举N次，每次枚举每一户人家，判断这一户人家是否被推销过，
找到选择哪一户人家会得到最大的疲劳值，累加到ans里即可。
注意：若选择在当前已选最靠右的一户人家（设为x）的左边的人家（设为y），
则答案只需要增加推销这户人家的疲劳值（即ans=ans+A[y]）。
而选择x右边的人家（设为z），则答案需要增加多出来的走路疲劳值和推销这户人家的疲劳值
（即ans=ans+(d[z]-d[x])*2+A[z]）。时间复杂度O(n2)
100%的数据：和60分数据差不多，
将枚举每一户人家改为用堆维护已选的最右边的那户人家（设为x）的左边推销疲劳值的最大值（
设为堆D1）和x的右边推销疲劳值加上来回走路疲劳值的最大值（设为堆D2）。
那么每次的答案就是ans=ans+max(D1[1],D2[1]-d[x]*2)。
求答案之前要判断D1[1]和D2[1]是否合法
（即D1[1]所对应的点在x左边且没选过，D2[1]所对应的点在x的右边且没选过）。
时间复杂度O(n log2 n)。
做模拟比赛的时候想了半天
想到了线段树？
然后线段树没有滑稽币不会啊
然后就果断打了个60分暴力QAQ
然后考完一看
这个堆优化不是很容易想到吗
唉果然被普及组吓坏了
都不敢想高级算法了直接交了个暴力
Orz我好害怕
说说我的理解吧
我们很容易看到
其实对于选择n个这个问题
可以贪心的
不难想到 X= i 时的最优方案一定从 X = i-1 时的最优方案的基础上再加一户宣传对象得来。
考虑 X = 1 时的选择，显然是所有住户中 Ai + 2Si 中最大的被选，
若有多个住户的 Ai + 2Si 相同，则优先选择 Si 最小的（想一想为什么）。
然后序列被划分成左右两个部分，选择左边住户获得 Ai 的贡献，
选择右边住户获得 Ai + 2(Si - T) 的贡献，T 表示当前划分界限到胡同入口的距离，
注意右边部分的贡献的大小关系相比最初并没有改变，只需要重新对左边住户的贡献进行排序。
于是可以建一个新优先队列将左边的所有住户加入，将原优先队列中被划分到左边部分的元素丢掉。
因为划分界线是一直往右移的，所以每个元素至多被加入两次，被删除两次，
说白了就是我们每次选一个最优
只有可能是两种情况
1.继续向右走扩大距离(这个情况肯定是要选择能得到最大疲劳值的点)
2.不继续向右走了(那么我们就直接在左边选一个推销疲劳值的最大的点了)
两种情况去最大就好了
考虑到范围很大
加了个堆(优先队列)优化咯
Orz就这样没了
*/
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN=100010;
int d[MAXN],a[MAXN];
int Last,Next,n,Sum,Best;
priority_queue<int> q;//堆用来维护已选的最右边的点左边的最大值

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}

void solve()
{
    Next=0;//Next用来记录下下一个最右边点的位置
    for(int k=1;k<=n;k++)
    {
        Last=Next;//已选的最右边的点
        if(!q.empty())//q非空(即不是第一次)
            Best=q.top()+d[Last]*2;//因为sum中只保存了所有选取的疲劳值而为保存走路的疲劳值
                                   //就是直接选取了左边的最优解
        else 
            Best=0;
        for(int i=Last+1;i<=n;i++)//尝试右边可不可以更新最大疲劳值
            if(a[i]+d[i]*2>Best)
            {
                Best=a[i]+d[i]*2;
                Next=i;//记录下更新的右边的店
            }
        printf("%d\n",Sum+Best);
        if(Next==Last)//如果没有更新到最右边的点
        {
            Sum+=q.top();//就直接选取堆中的点
            q.pop();//选完了出栈
        }
        else//说明选取的是右边的点
        {
            for(int i=Last+1;i<Next;i++)//更新了最右边的点那么左边的点要跟到来入栈
                q.push(a[i]);
            Sum+=a[Next];//选上了这个点
        }
    }
}

int main()
{
    init();
    solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n,sum[100010],q[100010],h[100010];
struct node{
    int s;
    int a;
}v[100010];

bool cmp(node x,node y){return x.a>y.a;}
int main()
{   
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].s; 
    for(int i=1;i<=n;i++)
        cin>>v[i].a;
    sort(v+1,v+1+n,cmp);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+v[i].a; 
    for(int i=1;i<=n;i++)
        q[i]=max(q[i-1],2*v[i].s);
    for(int i=n;i>=1;i--)
        h[i]=max(h[i+1],2*v[i].s+v[i].a);
    for(int i=1;i<=n;i++)
        cout<<max(sum[i]+q[i],sum[i-1]+h[i])<<"\n";
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
using namespace std;

namespace dts
{
    class node
    {
        public:
            int num,s,a;
    };
    class cmp1
    {
        public:
            int operator() (node a,node b)
            {
                return a.a+(a.s<<1)<b.a+(b.s<<1);
            }
    };
    class cmp2
    {
        public:
            int operator() (node a,node b)
            {
                return a.a<b.a;
            }
    };
    priority_queue<node,deque<node>,cmp1> h1;
    priority_queue<node,deque<node>,cmp2> h2;
    
    int n;
    vector<node> rec;
    
    int cmp_rec(node a,node b)
    {
        return a.s<b.s;
    }
    
    void main()
    {
        scanf("%d",&n);
        rec.resize(n);
        for (int i=0;i<n;i++)
            scanf("%d",&rec[i].s);
        for (int i=0;i<n;i++)
            scanf("%d",&rec[i].a);
        sort(&rec[0],&rec[n],cmp_rec);
        for (int i=0;i<n;i++)
            rec[i].num=i;
        for (int i=0;i<n;i++)
            h1.push(rec[i]);
        for (int i=0,pos=0,ans=0;!h1.empty()||!h2.empty();)
        {
            while (!h1.empty())
                if (h1.top().num<i)
                    h1.pop();
                else
                    break;
            if (h1.empty())
            {
                while (!h2.empty())
                {
                    ans+=h2.top().a;
                    h2.pop();
                    printf("%d\n",ans);
                }
                break;
            }
            if (h2.empty())
            {
                choose_h1:
                node now=h1.top();
                ans+=((now.s-pos)<<1)+now.a;
                pos=now.s;
                h1.pop();
                for (;i<=now.num-1;i++)
                    h2.push(rec[i]);
                i=now.num+1;
                printf("%d\n",ans);
                continue;
            }
            node n1=h1.top(),n2=h2.top();
            if (n1.a+((n1.s-pos)<<1)>n2.a)
                goto choose_h1;
            else
            {
                ans+=h2.top().a;
                h2.pop();
                printf("%d\n",ans);
            }
        }
    }
}

int main()
{
    dts::main();
}

rkbudlo大神的天才思路
你们写的都好多

#include<bits/stdc++.h>
using namespace std;
int Maxs[100005],Max[100005],sum[100005],n;
struct tzg{int s,x;}a[100005];
bool cmp(tzg x,tzg y){return x.x>y.x;}
int max(int x,int y){return x>y?x:y;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i].s);
    for(int i=1;i<=n;++i)scanf("%d",&a[i].x);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i].x;
    for(int i=1;i<=n;++i)Maxs[i]=max(Maxs[i-1],a[i].s);
    for(int i=n;i>=1;--i)Max[i]=max(Max[i+1],a[i].s*2+a[i].x);
    for(int i=1;i<=n;++i)printf("%d\n",max(sum[i-1]+Max[i],sum[i]+Maxs[i]*2));
    return 0;
}

用堆做的,程序在我校的标准数据中是通过的，然而vj不知为啥不过，求指点
编译成功

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(44,32) Warning: range check error while evaluating constants (-1 must be between 0 and 4294967295)
foo.pas(4,10) Note: Local variable "tmax" not used
Linking foo.exe
72 lines compiled, 0.0 sec, 28240 bytes code, 1268 bytes data
1 warning(s) issued
1 note(s) issued

测试数据 #0: Accepted, time = 0 ms, mem = 3940 KiB, score = 10

测试数据 #1: WrongAnswer, time = 0 ms, mem = 3940 KiB, score = 0

测试数据 #2: WrongAnswer, time = 0 ms, mem = 3940 KiB, score = 0

测试数据 #3: Accepted, time = 15 ms, mem = 3940 KiB, score = 10

测试数据 #4: WrongAnswer, time = 15 ms, mem = 3940 KiB, score = 0

测试数据 #5: Accepted, time = 0 ms, mem = 3936 KiB, score = 10

测试数据 #6: RuntimeError, time = 31 ms, mem = 3936 KiB, score = 0

测试数据 #7: RuntimeError, time = 31 ms, mem = 3940 KiB, score = 0

测试数据 #8: RuntimeError, time = 46 ms, mem = 3940 KiB, score = 0

测试数据 #9: RuntimeError, time = 31 ms, mem = 3940 KiB, score = 0

RuntimeError, time = 169 ms, mem = 3940 KiB, score = 30
代码
```pascal
//const bind=array[0..200001] of longint;
var //heap:bind;
heap,jli,pl,ans:array[0..200001] of longint;
i,j,len,tmax,ti,li,n:longint;

procedure swap(var a,b:longint);
var t:longint;
begin t:=a;a:=b;b:=t;end;

procedure put(a:longint);
var i:longint;
begin
inc(len);
heap[len]:=a;
i:=len;
while (heap[i]>heap[i>>1])and(i<>1) do begin
swap(heap[i],heap[i>>1]);
i:=i>>1;
end;
end;

function get:longint;
var i,t:longint;
begin
get:=heap[1];
heap[1]:=heap[len];
heap[len]:=-1;
dec(len);i:=1;
if len=0 then exit;
while true do begin
t:=i<<1;
if (heap[i]<heap[t])and(heap[t]>heap[t+1])and(heap[t]<>-1)then begin
swap(heap[i],heap[t]);i:=t;end
else if (heap[i]<heap[t+1])and(heap[t+1]<>-1)then begin
swap(heap[i],heap[t+1]);i:=t+1;end
else break;
end;
end;

begin
//assign(input,'salesman.in'); assign(output,'salesman.out');
//reset(input); rewrite(output);
read(n);
filldword(heap,length(heap),-1);
//filldword(d2,length(d2),maxlongint);
//le[0]:=0;
for i:=1 to n do read(jli[i]);
for i:=1 to n do read(pl[i]);
//l1:=0;l2:=0;
//ans[1]:=get(d2,l2,l1);
ans[1]:=pl[n]+jli[n]<<1;
li:=1;ti:=n;
for j:=n-1 downto 1 do if pl[j]+jli[j]<<1>ans[1] then begin
ans[1]:=pl[j]+jli[j]<<1;ti:=j;
end;
for i:=1 to ti-1 do put(pl[i]);
li:=ti;
//for j:=1 to len do write(heap[j],' ');writeln;
writeln(ans[1]);

for i:=2 to n do begin
//writeln('li=',li);
ans[i]:=0;
for j:=n downto li+1 do if pl[j]+(jli[j]-jli[li])<<1>ans[i] then begin
ans[i]:=pl[j]+(jli[j]-jli[li])<<1;ti:=j;//writeln('le');
end;
for j:=li+1 to ti-1 do put(pl[i]);//if i=5 then writeln(ans[i]);
if (heap[1]>ans[i]) then ans[i]:=get else li:=ti;
//for j:=1 to 5 do write(heap[j],' ');writeln;
inc(ans[i],ans[pred(i)]);writeln(ans[i]);
end;
//close(input); close(output);
end.
```

大神们能帮我看看么？？少了第一个输出
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <list>
#include <cstdio>
#include <deque>
#include <cstring>
#include <stdlib.h>

using namespace std;
int comp(int a,int b)
{
return a>b;
}
int main()
{
freopen("salesman.in","r",stdin);
freopen("salesman.out","w",stdout);
long n,tie[100000],pt[100000],sum[100000],pp[100000],s;
cin>>n;
for(int i=1;i<=n;++i)
cin>>pt[i];
for(int i=1;i<=n;++i)
{
cin>>tie[i];
pt[i]=pt[i]*2+tie[i];
}
for(int i=2;i<=n;++i)
{
for(int l=1;l<=n;++l)
pp[l]=tie[l];
for(int k=i;k<=n;++k)
{
sort(pp+1,pp+k-1,comp);
for(int j=1;j<=i-1;++j)
s=s+pp[j];
sum[k]=pt[k]+s;
s=0;
}
sort(sum+i,sum+n,comp);
cout<<sum[i]<<endl;
memset(sum,0,sizeof(sum));
}
return 0;
}

Var
     i,j:longint;
     max,num,n:int64;
     a,b:array[1..1000000]of int64;

Procedure kp(l,r:int64);
Var
     i,j,t,mid:int64;
Begin
     i:=l; j:=r; mid:=b[(i+j) div 2];
     repeat
          while b[i]>mid do inc(i);
          while b[j]<mid do dec(j);
          if i<=j then
          begin
               t:=b[i]; b[i]:=b[j]; b[j]:=t;
               t:=a[i]; a[i]:=a[j]; a[j]:=t;
               inc(i); dec(j);
          end;
     until i>j;
     if i<r then kp(i,r);
     if l<j then kp(l,j);
End;

Begin
     readln(n);
     for i:=1 to n-1 do
          read(a[i]);
     readln(a[n]);
     for i:=1 to n-1 do
          read(b[i]);
     readln(b[n]);
     max:=-1;
     for i:=1 to n do
          if max<a[i]*2+b[i] then
          begin
               j:=i;
               max:=a[i]*2+b[i];
          end;
     b[j]:=0;
     writeln(max);
     num:=max-a[j]*2;
     kp(1,n);
     i:=0;
     while i<n-1 do
     begin
          inc(i);
          num:=num+b[i];
          if num+a[i]*2>max+b[i] then
               max:=num+a[i]*2
          else
               if num+a[i]*2<=max+b[i] then
                    max:=max+b[i];
          writeln(max);
     end;
     readln;
End.

不科学啊。。这个放到洛谷是全对的啊、
#1
AC
0ms/9269kB

#2
AC
52ms/9269kB

#3
AC
0ms/9269kB

#4
AC
0ms/9269kB

#5
AC
0ms/9269kB

#6
AC
0ms/9269kB

#7
AC
0ms/9269kB
#8
AC
55ms/9269kB

#9
AC
51ms/9269kB

#10
AC
61ms/9269kB
在这里就不对。。。。vijos测试数据有问题》？？？

var a,s,p,sum,b,c,m1,m2,f:array[0..100000] of longint;
n,i,j:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
procedure qsort(l,r:longint);
var i,j,k,t,t1,t2:longint;
begin
i:=l; j:=r; k:=(i+j) div 2;
t:=a[k]; a[k]:=a[i];
t1:=p[k]; p[k]:=p[i];
while i<j do
begin
while (i<j)and(a[j]<t) do dec(j);
if i<j then
begin
a[i]:=a[j];
p[i]:=p[j];
inc(i);
end;
while (i<j)and(a[i]>t) do inc(i);
if i<j then
begin
a[j]:=a[i];
p[j]:=p[i];
dec(j);
end;
end;
p[i]:=t1;
if i-1>l then qsort(l,i-1);
if i+1<r then qsort(i+1,r);
end;
begin
assign(input,'salesman.in');
assign(output,'salesman.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(s[i]);
readln;
for i:=1 to n do
begin
read(a[i]);
p[i]:=i;
end;
b:=a;
qsort(1,n);
a:=b;
sum[1]:=a[p[1]];
m1[1]:=p[1];
for i:=2 to n do
begin
sum[i]:=sum[i-1]+a[p[i]];
if s[m1[i-1]]>s[p[i]] then m1[i]:=m1[i-1]
else m1[i]:=p[i];
end;
m2[n]:=p[n];
for i:=n-1 downto 1 do
begin
if 2*s[m2[i+1]]+a[m2[i+1]]>2*s[p[i]]+a[p[i]] then m2[i]:=m2[i+1]
else m2[i]:=p[i];
end;
for i:=1 to n do
writeln(max(sum[i-1]+a[m2[i]]+max(s[m1[i-1]],s[m2[i]])*2,sum[i]+s[m1[i]]*2));
close(input);
close(output);
end.

贪心
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct data{
long long dis;
long long tired;
};
data info[100010];
long long g[100010]={0},h[100010]={0},x[100010]={0},f[100010]={0};
bool cmp(data a,data b){
return a.tired<b.tired;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&info[i].dis);
for(int i=1;i<=n;i++) scanf("%d",&info[i].tired);
sort(info,info+n+1,cmp);
for(int i=1;i<=n;i++) g[i]=max(info[i].dis*2+info[i].tired,g[i-1]);
h[n]=2*info[n].dis;
for(int i=n;i>=1;i--) h[i]=max(h[i+1],info[i].dis*2);
for(int i=n;i>=1;i--) x[i]=x[i+1]+info[i].tired;
for(int i=n;i>=1;i--){
f[i]=x[i]+h[i];
f[i]=max(f[i],x[i+1]+g[i-1]);
}
for(int i=n;i>=1;i--) printf("%d\n",f[i]);
return 0;
}

树状数组？

http://blog.csdn.net/u013598409/article/details/53025285
这道题的正解是堆。
膜拜yww大神。
```c++
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)

#define x first
#define y second
#define mp make_pair

typedef pair<int,int> PII;

const int N=131072;

int n;
int s[N],a[N];

int cur,vis[N];
priority_queue<PII> qs,qb;
int res;

inline int rd(void)
{
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}

int main(void)
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);

n=rd();
rep(i,1,n) s[i]=rd();
rep(i,1,n) a[i]=rd();

rep(i,1,n)
qb.push(mp(2*s[i]+a[i],i));

PII t1,t2; int e1,e2,cs;
rep(i,1,n)
{
while (!qs.empty())
{
t1=qs.top();
if (vis[t1.y])
qs.pop();
else break;
}
while (!qb.empty())
{
t2=qb.top();
if (t2.y<cur||vis[t2.y])
qb.pop();
else break;
}

e1=(!qs.empty());
e2=(!qb.empty());
if (!e1&&e2)
cs=2;
else if (e1&&!e2)
cs=1;
else if (e1&&e2)
{
t1=qs.top(),t2=qb.top();
if (t2.x-2*s[cur]>=t1.x)
cs=2;
else cs=1;
}

if (cs==1)
{
t1=qs.top(); qs.pop();
vis[t1.y]=1;
res+=t1.x;
}
else if (cs==2)
{
t2=qb.top(); qb.pop();
vis[t2.y]=1;
rep(j,cur+1,t2.y)
if (!vis[j])
qs.push(mp(a[j],j));
res+=(t2.x-2*s[cur]);
cur=t2.y;
}

printf("%d\n",res);
}

return 0;
}
```

单调队列+优先队列

只需要两个堆

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
typedef long long ll;
int s[100010];
int a[100010];
int b[100010];
typedef pair<int,int> pa;
priority_queue<pa> q1,q2;
int main()
{
memset(b,0,sizeof(b));
int n;
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
int x=0;
for(i=1;i<=n;i++)
q2.push(make_pair(a[i]+2*s[i],i));
int ans=0;
for(i=1;i<=n;i++)
{
while(!q1.empty()&&b[q1.top().second])
q1.pop();
while(!q2.empty()&&(b[q2.top().second]||q2.top().second<=x))
q2.pop();
int t1=-1,t2=-1;
if(!q1.empty())
t1=q1.top().first;
if(!q2.empty())
t2=q2.top().first-2*s[x];
if(t1>t2)
{
b[q1.top().second]=1;
ans+=t1;
q1.pop();
}
else
{
b[q2.top().second]=1;
ans+=t2;
while(x<q2.top().second)
{
x++;
q1.push(make_pair(a[x],x));
}
q2.pop();
}
printf("%d\n",ans);
}
return 0;
}


不错的好题！
用构造反证法可以证明，每一次最大都是在前一次基础上增加一个；或者说，每一次最大都是在后一次基础上减少一个。不难发现后一种思路适合使用线段树求解。
一个棘手的问题是：**如果改变的是最远点，走路疲劳会减少**。不妨增加一个特判，每次把最远的点和次远的点找到，把最远点的疲劳度加上最远点到次远点距离的二倍作为增量。
那么问题就转化为如何找到最远点和次远点。不难发现最远点和次远点都是单调的，因此可以用摊还O(1)的时间找到他们。这样问题就解决了。总的时间复杂度为O(nlgn+n)=O(nlgn)。
- 测试数据 #0: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
- 测试数据 #1: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
- 测试数据 #2: Accepted, time = 15 ms, mem = 9164 KiB, score = 10
- 测试数据 #3: Accepted, time = 0 ms, mem = 9160 KiB, score = 10
- 测试数据 #4: Accepted, time = 0 ms, mem = 9164 KiB, score = 10
- 测试数据 #5: Accepted, time = 15 ms, mem = 9164 KiB, score = 10
- 测试数据 #6: Accepted, time = 125 ms, mem = 9164 KiB, score = 10
- 测试数据 #7: Accepted, time = 93 ms, mem = 9164 KiB, score = 10
- 测试数据 #8: Accepted, time = 125 ms, mem = 9164 KiB, score = 10
- 测试数据 #9: Accepted, time = 125 ms, mem = 9168 KiB, score = 10

Accepted, time = 498 ms, mem = 9168 KiB, score = 100
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

class zkw {
long long arr[400005], max_pos[400005];
int n;
public:
zkw()
{
memset(arr, 127, sizeof arr);
n = 1<<17;
for (int i = n; i < n+n; i++)
max_pos[i] = i-n+1;
}
inline int pos(int i)
{
return i + n - 1;
}
inline void fix(int i)
{
arr[i] = min(arr[i<<1], arr[(i<<1)+1]);
max_pos[i] = arr[i] == arr[i<<1] ? max_pos[i<<1] : max_pos[(i<<1)+1];
if (i > 1)
fix(i >> 1);
}
inline void modify(int i, int j)
{
int t = pos(i);
arr[t] = j;
fix(t >> 1);
}
inline long long top()
{
return arr[1];
}
inline int top_pos()
{
return max_pos[1];
}
inline long long in(int i)
{
return arr[pos(i)];
}
}zkwheap;

long long n;
long long len[100005], A[100005];
long long ans[100005];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &len[i]);
A[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
zkwheap.modify(i, A[i]);
A[i] += A[i-1];
}
ans[n] = A[n]+len[n]+len[n];
int first = n, second = n-1;
zkwheap.modify(n, zkwheap.in(n)+2*(len[n]-len[n-1]));
for (int i = n-1; i >= 1; i--) {
int tp = zkwheap.top_pos();
long long val = zkwheap.top();
ans[i] = ans[i+1] - val;
zkwheap.modify(tp, 1000000000);
if (second == tp) {
while (zkwheap.in(second) >= 10000000)
second--;
zkwheap.modify(first, A[first]-A[first-1]+2*(len[first]-len[second]));
}
if (first == tp) {
first = second;
while (first == second || zkwheap.in(second) >= 10000000)
second--;
zkwheap.modify(first, zkwheap.in(first)+2*(len[first]-len[second]));
}
}
for (int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100000+2;
int ss[maxn],aa[maxn];
bool idx[maxn];
struct hh{
int s,h,xu;
friend bool operator>(hh a,hh b) {if (a.h!=b.h) return a.h<b.h;else return a.s<b.s;}
hh(int a=0,int b=0,int c=0){s=a;h=b;xu=c;}
};
int main(){
// freopen("salesman.txt","r",stdin);
// freopen("my.txt","w",stdout);
memset(idx,0,sizeof(idx));
int n;
cin>>n;
priority_queue<int,vector<int>,less<int > >q1;
priority_queue<hh,vector<hh>,greater<hh> >q2;
for(int i=0;i<n;i++) scanf("%d",&ss[i]);
for(int i=0;i<n;i++){
scanf("%d",&aa[i]);
q2.push(hh(ss[i],ss[i]*2+aa[i],i));
}
hh q2m=q2.top();q2.pop();
int m=q2m.h,c=q2m.s,x=q2m.xu,x0=0;idx[x]=1;
for(int i=0;i<n;i++){
printf("%d\n",m);
if(i==n-1) break;
int q1m=0;q2m.h=0;
for(int i=x0;i<x;i++) if(!idx[i]) q1.push(aa[i]);
x0=x+1;q1m=q1.top();
while(!q2.empty()){
q2m=q2.top();
if(q2m.xu>x) break;
q2.pop();
}
q2m.h-=c*2;
if(q2m.h>q1m) {
q2.pop();m+=q2m.h;c=q2m.s;x=q2m.xu;idx[x]=1;/*printf("%d->%d**\n",q2m.xu,q2m.h);*/
}
else {
q1.pop();m+=q1m;/*printf("%d->**\n",q1m);*/
}
}
return 0;
}

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(31,26) Warning: Variable "max" does not seem to be initialized
Linking foo.exe
51 lines compiled, 0.1 sec, 28240 bytes code, 1268 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 1588 KiB, score = 10
测试数据 #1: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
测试数据 #2: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
测试数据 #3: WrongAnswer, time = 0 ms, mem = 1584 KiB, score = 0
测试数据 #4: WrongAnswer, time = 15 ms, mem = 1588 KiB, score = 0
测试数据 #5: WrongAnswer, time = 0 ms, mem = 1580 KiB, score = 0
测试数据 #6: WrongAnswer, time = 406 ms, mem = 1584 KiB, score = 0
测试数据 #7: Accepted, time = 203 ms, mem = 1584 KiB, score = 10
测试数据 #8: WrongAnswer, time = 250 ms, mem = 1592 KiB, score = 0
测试数据 #9: WrongAnswer, time = 328 ms, mem = 1580 KiB, score = 0
WrongAnswer, time = 1202 ms, mem = 1592 KiB, score = 20
呵呵！在noip标准数据上过的代码~

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long m,q[100011],w[100011],a[100011],l,s,ans;
long long cut()
{
int m=a[1],x=1,y=2;
a[1]=a[s];
s--;
while(y<=s&&(a[x]<a[y]||a[x]<a[y+1]))
{
if(y<s&&a[y]<a[y+1])y++;
int t=a[x];
a[x]=a[y];
a[y]=t;
x=y;
y=2*y;
}
return m;
}
void charu(int k)
{
int x=k,si=++s;
while(k>a[si/2]&&si>1)
{
a[si]=a[si/2];
si/=2;
}
a[si]=x;
}
int main()
{
scanf("%lld",&m);
for(int i=1;i<=m;i++)
scanf("%lld",&q[i]);
for(int i=1;i<=m;i++)
scanf("%lld",&w[i]);
long long b=0,c=0,xc=-1;
for(int i=1;i<=m;i++)
{
for(int j=l+1;j<=m;j++)
{
int k=(q[j]-l)*2+w[j];
if(k>c){xc=j;c=k;}
}
if(c>b)
{
ans+=c;
for(int j=l+1;j<xc;j++)
charu(w[j]);
l=xc;
c=0;
}
else
ans+=b;
b=cut();
printf("%lld\n",ans);
}
return 0;
}

//刚刚那个不规范 求指点
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
long zhuhu[100001][2];
long meigezhuhudezhi[100001], linshizongzhi[100001], jieguo[100001];

long main(void) {

long max, i, j;
scanf("%ld", &max);
for (i = 0;i < max;i++)
scanf("%ld", &zhuhu[i][0]);//记录距离
for (i = 0;i < max;i++)
scanf("%ld", &zhuhu[i][1]);//记录产品疲劳值
long dangqianzuileizhuhu = 0;
for (i = 0;i < max;i++) {
linshizongzhi[i] = 2 * zhuhu[i][0] + zhuhu[i][1];
if (linshizongzhi[dangqianzuileizhuhu] < linshizongzhi[i])
dangqianzuileizhuhu = i;

}
jieguo[0] = linshizongzhi[dangqianzuileizhuhu];
long temp;
for (i = 0;i < max;i++)
{
/* temp = zhuhu[dangqianzuileizhuhu][0] - zhuhu[i][0];
if (temp < 0)
linshizongzhi[i]=2*abs(zhuhu[dangqianzuileizhuhu][0] - zhuhu[i][0]);
else linshizongzhi[i] -= zhuhu[i][0];*/

if (i < dangqianzuileizhuhu)
linshizongzhi[i] -= 2 * zhuhu[i][0];
else
linshizongzhi[i] += 2 * (zhuhu[i][0] - zhuhu[dangqianzuileizhuhu][0]) - 2 * zhuhu[i][0];
}
linshizongzhi[dangqianzuileizhuhu] = 0;
long l = 1;
for (i = 0;i < max;i++) {
temp = 0;
for (j = 0;j < max;j++)
if (linshizongzhi[temp] < linshizongzhi[j])
temp = j;
jieguo[l] = jieguo[l - 1] + linshizongzhi[temp];
linshizongzhi[temp] = 0;
l++;
}
for (i = 0;i < max;i++) {
printf("%ld\n", jieguo[i]);
}
// system("pause");
}