[NOIP2015]推销员

#include<iostream>
using namespace std;
int a[100005];
int b[100005];
int dp[100005];
int tmp[2][100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    int Max=0;
    for(int i=1;i<=n;i++){
        tmp[1][i]=b[i];
        dp[i]=a[i]*2+b[i];
        if(dp[i]>Max) Max=dp[i];
        if(tmp[1][i-1]>tmp[1][i])
            tmp[1][i]=tmp[1][i-1];
    }
    printf("%d\n",Max);
    for(int k=2;k<=n;k++){
        int Max=0;
        for(int j=k;j<=n;j++){
            dp[j]=a[j]*2+b[j]+tmp[(k-1)%2][j-1];
            tmp[k%2][j]=tmp[(k-1)%2][j-1]+b[j];
            if(Max<dp[j]) Max=dp[j];
            if(tmp[k%2][j-1]>tmp[k%2][j])
            tmp[k%2][j]=tmp[k%2][j-1];
        }
        printf("%d\n",Max);
    }
}

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

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
const int maxN = 1e5 + 7;


int n; 
int dist[maxN], cost[maxN];
int suffixMax[maxN]; //记录dist的后缀最大值 
int f[maxN]; // f[i]表示当X=1时在1~i范围内只选择1家住户的最优解 
int prefixSum[maxN]; // cost的前缀和 

int getSum(int x, int y){
    return x < y ? prefixSum[y] - prefixSum[x] : 0;
}

void mergeSort(int l, int r){
    if(l >= r) return;
    int mid = (l+r) >> 1;
    
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    
    int tmp1[r-l+1], tmp2[r-l+1];
    int i = l, j = mid + 1, k = 0;
    
    while(i <= mid && j <= r){
        if(cost[i] > cost[j] || cost[i] == cost[j] && dist[i] > dist[j]){
            tmp1[k] = cost[j];
            tmp2[k++] = dist[j++];
        }
        else{
            tmp1[k] = cost[i];
            tmp2[k++] = dist[i++];
        }
    }
    while(i <= mid){
        tmp1[k] = cost[i];
        tmp2[k++] = dist[i];
        ++i;
    }
    while(j <= r){
        tmp1[k] = cost[j];
        tmp2[k++] = dist[j];
        ++j;
    }
    
    rep(i, k){
        cost[i+l] = tmp1[i];
        dist[i+l] = tmp2[i];
    }
}

int main(){
    scanf("%d", &n);
    For(i, 1, n) dist[i] = ri();
    For(i, 1, n) cost[i] = ri();
    
    mergeSort(1, n);
    rFor(i, n, 1) suffixMax[i] = max(suffixMax[i+1], dist[i]);
    
    For(i, 1, n) f[i] = max(f[i-1], cost[i] + dist[i]*2);
    
    For(i, 1, n) prefixSum[i] = prefixSum[i-1] + cost[i];
    
    rFor(i, n, 1) printf("%d\n", max(getSum(i, n) + f[i], getSum(i-1, n) + 2*suffixMax[i]));
    return 0;
}