比赛 Asm.Def战记之圣地亚哥“杯2015 评测结果 TTRTTTTTTT
题目名称 Asm.Def的枪榴弹 最终得分 0
用户昵称 321Rain 运行时间 9.016 s
代码语言 C++ 内存使用 1.86 MiB
提交时间 2015-10-31 11:34:08
显示代码纯文本
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct N{
	int a,b,c,d,e,add;
}p[100];
struct M{
	int to,dist;
};
int n,k1,k2,k3;
int f[15][15][15];
int add[20];
int dis[100100];
vector<M> pi[100100];
int bi(N a,N b)
{
	if (a.add>b.add) return 1;
	return 0;
}
bool pan(int i)
{
	if (k1+k3>=p[i].a&&k2+k3+k1-p[i].a>=p[i].b)
	 return true;
	return false;
}
void spfa(int x)
{
	int time[100100]={0};
	bool vis[100100];
	queue<int>q;
	for (int i=1;i<=n;i++)
	 dis[i]=-1,vis[i]=false;
	dis[x]=p[x].add;
	q.push(x);
	while (!q.empty())
	{
		int k=q.front();
		vis[k]=false;
		q.pop();
		for (int i=0;i<pi[k].size();i++)
		{
			M&e=pi[k][i];
			//cout<<e.to<<" "<<e.dist<<"*"<<endl;
			if (pan(e.to)&&(dis[e.to]==-1||dis[e.to]<dis[k]+e.dist))
			{
				dis[e.to]=dis[k]+e.dist;
				if (k1>=p[e.to].a&&k2>=p[e.to].b)
				{
				  k1=k1-p[e.to].a+p[e.to].c;
				  k2=k2-p[e.to].b+p[e.to].d;
			      k3+=p[e.to].e;
				}
				else if (k1<p[e.to].a&&k2<p[e.to].b)
				{
					k1=p[e.to].c;
					k2=p[e.to].d;
					k3=k3+k2+k1-p[e.to].a-p[e.to].b+p[e.to].e;
				}
				else if (k1<p[e.to].a&&k2>=p[e.to].b)
				{
					k1=p[e.to].c;
					k2=k2-p[e.to].b+p[e.to].d;
					k3=k3+k1-p[e.to].a+p[e.to].e;
				}
				else 
				{
					k1=k1-p[e.to].a+p[e.to].c;
					k2=p[e.to].d;
					k3=k3+k2-p[e.to].b+p[e.to].e;
				}
				if (!vis[e.to])
				{
					vis[e.to]=true;
					q.push(e.to);
				}
			}
		}
	}
}
int main()
{
	freopen("asm_grenade.in","r",stdin);
	freopen("asm_grenade.out","W",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	 cin>>p[i].a;
	for (int i=1;i<=n;i++)
	 cin>>p[i].b;
	for (int i=1;i<=n;i++)
	 cin>>p[i].c;
	for (int i=1;i<=n;i++)
	 cin>>p[i].d;
	for (int i=1;i<=n;i++)
	 cin>>p[i].e;
	for (int i=1;i<=n;i++)
	 p[i].add=p[i].c+p[i].d+p[i].e-p[i].a-p[i].b;
	cin>>k1>>k2>>k3;
	int ans=-10000000;
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
     {
       if (i!=j)
       {
       	 pi[i].push_back((M){j,p[j].add});
	   }
	 }
	for (int i=1;i<=n;i++)
	{
		if (pan(i))
		spfa(i);
		for (int j=1;j<=n;j++)
		 ans=max(ans,dis[j]);
	}
	cout<<ans;
	return 0;
}