比赛 20110724 评测结果 AAATTTTTTT
题目名称 准备工作 最终得分 30
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-24 11:51:24
显示代码纯文本
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN=105;
const int oo=~0u>>2;

struct Node
{
	int P,R,D;
	bool operator < (const Node &b) const
	{
		return D<b.D || (D==b.D && R<b.R);
	}
}Work[MAXN];

int N;

inline void Max(int &a,int b)
{
	if (b>a)
		a=b;
}

int main()
{
	freopen("preparation.in","r",stdin);
	freopen("preparation.out","w",stdout);
	while(true)
	{
		scanf("%d",&N);
		if (N==0)
			break;
		for(int i=0;i<N;i++)
			scanf("%d",&Work[i].P);
		for(int i=0;i<N;i++)
			scanf("%d",&Work[i].R);
		for(int i=0;i<N;i++)
			scanf("%d",&Work[i].D);
		sort(Work,Work+N);
		vector<int> v(N);
		for(int i=0;i<N;i++)
			v[i]=i;
		int re=oo;
		int tot=0;
		do
		{
			tot++;
			int now=0,ans=-oo;
			for(int i=0;i<N;i++)
			{
				if (now<Work[v[i]].R)
					now=Work[v[i]].R;
				now+=Work[v[i]].P;
				Max(ans,now-Work[v[i]].D);
			}
			if (ans<re)
				re=ans;
		}while(next_permutation(v.begin(),v.end()) && tot<=10000000);
		printf("%d\n",re);
	}
	return 0;
}