比赛 Asm.Def战记之圣地亚哥“杯2015 评测结果 AAAAAAAAAA
题目名称 Asm.Def的枪榴弹 最终得分 100
用户昵称 jekyll 运行时间 0.286 s
代码语言 C++ 内存使用 22.79 MiB
提交时间 2019-10-23 17:54:25
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

const int maxn=145;

inline int read(){
	register int x=0,w=1,ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-48;
	return w*x;
}

int n,k0,k1,k2;
int a[maxn],b[maxn],c[maxn],d[maxn],e[maxn];
int f[1<<14][maxn],sum[1<<14];

int main(){
	freopen("asm_grenade.in","r",stdin);
	freopen("asm_grenade.out","w",stdout);
	n=read();
	for(int i=0;i<n;i++)a[i]=read();
	for(int i=0;i<n;i++)b[i]=read();
	for(int i=0;i<n;i++)c[i]=read();
	for(int i=0;i<n;i++)d[i]=read();
	for(int i=0;i<n;i++)e[i]=read();
	k0=read(),k1=read(),k2=read();
	memset(f,0xff,sizeof f);
	sum[0]=k0+k1+k2;f[0][k0]=k2;
	for(int i=1,j;i<(1<<n);i++){
		for(j=0;j<n;j++)
			if((i>>j)&1)break;
		sum[i]=sum[i-(1<<j)]+c[j]+d[j]+e[j]-a[j]-b[j];
	}
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<=sum[i];j++){
			int A=j,B=sum[i]-j-f[i][j],C=f[i][j];
			for(int k=0;k<n;k++){
				if((i>>k)&1)continue;
				int na=A-a[k],nb=B-b[k],nc=C;
				if(na<0)nc+=na,na=0;
				if(nb<0)nc+=nb,nb=0;
				if(nc<0)continue;
				f[i|(1<<k)][na+c[k]]=max(f[i|(1<<k)][na+c[k]],nc+e[k]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<=sum[i];j++)
			if(f[i][j]!=-1)ans=max(ans,sum[i]);
	cout<<ans<<'\n';
}
/*
3
1 0 6
0 1 0
1 1 10
1 1 10
0 0 10
0 0 5
*/