这数据太水了吧（题解）

贪心＋枚举（其他网站60） magicoj：啥呀，100分的好吧

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,ans,maxx;
struct house{
	int s;
	int t;
	//int node;
}a[N];
bool cmp1(house x,house y)
{
	if(x.t+x.s>y.t+y.s)
	{
		return 1;
	}
	else
	{
		return 0;
	}
} 
bool cmp2(house x,house y)
{
	int ty=y.t-maxx,tx=x.t-maxx;
	if(ty>0 && tx>0)
	{
		return tx+x.s>ty+y.s;
	}
	else if(tx>0)
	{
		return tx+x.s>y.s;
	}
	else if(ty>0)
	{
		return x.s>ty+y.s;
	}
	else
	{
		return x.s>y.s;
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i].t;
		a[i].t<<=1;
	}
	for(int i=1;i<=n;++i)
	{
		cin>>a[i].s;
		//a[i].node=i;
	}
	sort(a+1,a+n+1,cmp1);
	ans=a[1].s+a[1].t;
	maxx=a[1].t;
	//cout<<"choose "<<a[1].node<<":"
	cout<<ans<<endl;
	for(int i=2;i<=n;++i)
	{
		sort(a+i,a+n+1,cmp2);
		ans+=a[i].s;
		if(a[i].t>maxx)
		{
			ans-=maxx;
			maxx=a[i].t;
			ans+=maxx;
		}
		//cout<<"choose "<<a[i].node<<":";
		cout<<ans<<endl;
	}
	return 0;
}

正解：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
 
const int maxn=100010;
int n;
int sum[maxn];
int f[maxn];
int b[maxn];
 
struct home{
	int s;
	int a;
}h[maxn];
 
bool cmp(const home &a,const home &b){
	return a.a>b.a;
}
 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i].s;
	for(int i=1;i<=n;i++) cin>>h[i].a;
	sort(h+1,h+1+n,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+h[i].a;
	for(int i=1;i<=n;i++) f[i]=max(f[i-1],2*h[i].s);
	for(int i=n;i>=1;i--) b[i]=max(b[i+1],2*h[i].s+h[i].a);
	for(int i=1;i<=n;i++) cout<<max(sum[i]+f[i],sum[i-1]+b[i])<<endl;
	return 0;
}

PS:甚至0ms我哭死