NOIP2015普及组复赛A 推销员

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3  
  4 #define rep(i,n) for (int i = 0; i < (n); ++i)
  5 #define For(i,s,t) for (int i = (s); i <= (t); ++i)
  6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i)
  7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
  8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
  9  
 10 #define pr(x) cout << #x << " = " << x << "  "
 11 #define prln(x) cout << #x << " = " << x << endl
 12  
 13 #define ALL(x) x.begin(),x.end()
 14 #define INS(x) inserter(x,x.begin())
 15  
 16 #define ms0(a) memset(a,0,sizeof(a))
 17 #define msI(a) memset(a,inf,sizeof(a))
 18  
 19 #define pii pair<int,int> 
 20 #define piii pair<pair<int,int>,int> 
 21 #define mp make_pair
 22 #define pb push_back
 23 #define fi first
 24 #define se second
 25  
 26 inline int gc(){
 27     static const int BUF = 1e7;
 28     static char buf[BUF], *bg = buf + BUF, *ed = bg;
 29      
 30     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
 31     return *bg++;
 32 } 
 33  
 34 inline int ri(){
 35     int x = 0, f = 1, c = gc();
 36     for(; c<48||c>57; f = c==‘-‘?-1:f, c=gc());
 37     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
 38     return x*f;
 39 }
 40  
 41 typedef long long LL;
 42 const int maxN = 1e5 + 7;
 43  
 44 int n; 
 45 int dist[maxN], cost[maxN];
 46 int suffixMax[maxN]; //记录dist的后缀最大值 
 47 int f[maxN]; // f[i]表示当X=1时在1~i范围内只选择1家住户的最优解 
 48 int prefixSum[maxN]; // cost的前缀和 
 49  
 50 int getSum(int x, int y){
 51     return x < y ? prefixSum[y] - prefixSum[x] : 0;
 52 }
 53  
 54 void mergeSort(int l, int r){
 55     if(l >= r) return;
 56     int mid = (l+r) >> 1;
 57      
 58     mergeSort(l, mid);
 59     mergeSort(mid+1, r);
 60      
 61     int tmp1[r-l+1], tmp2[r-l+1];
 62     int i = l, j = mid + 1, k = 0;
 63      
 64     while(i <= mid && j <= r){
 65         if(cost[i] > cost[j] || cost[i] == cost[j] && dist[i] > dist[j]){
 66             tmp1[k] = cost[j];
 67             tmp2[k++] = dist[j++];
 68         }
 69         else{
 70             tmp1[k] = cost[i];
 71             tmp2[k++] = dist[i++];
 72         }
 73     }
 74     while(i <= mid){
 75         tmp1[k] = cost[i];
 76         tmp2[k++] = dist[i];
 77         ++i;
 78     }
 79     while(j <= r){
 80         tmp1[k] = cost[j];
 81         tmp2[k++] = dist[j];
 82         ++j;
 83     }
 84      
 85     rep(i, k){
 86         cost[i+l] = tmp1[i];
 87         dist[i+l] = tmp2[i];
 88     }
 89 }
 90  
 91 int main(){
 92     scanf("%d", &n);
 93     For(i, 1, n) dist[i] = ri();
 94     For(i, 1, n) cost[i] = ri();
 95      
 96     mergeSort(1, n);
 97     rFor(i, n, 1) suffixMax[i] = max(suffixMax[i+1], dist[i]);
 98      
 99     For(i, 1, n) f[i] = max(f[i-1], cost[i] + dist[i]*2);
100      
101     For(i, 1, n) prefixSum[i] = prefixSum[i-1] + cost[i];
102      
103     rFor(i, n, 1) printf("%d\n", max(getSum(i, n) + f[i], getSum(i-1, n) + 2*suffixMax[i]));
104     return 0;
105 }