记录编号	126480	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Nov13] 不设找零	最终得分	100
用户昵称	Ezio	是否通过	通过
代码语言	C++	运行时间	0.403 s
提交时间	2014-10-13 08:38:06	内存使用	4.35 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <queue>
#include <map>
#include <vector>
#define scafn scanf
#define For(st,ed,i) for(int i=st;i<=ed;++i)
#define Fordown(st,ed,i) for(int i=st;i>=ed;--i)
#define start(a,flag) memset(a,flag,sizeof(a));
using namespace std;
typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;
const int INF=0x7fffffff;const int inf=0xfffffff; 
int coin[17],a[100010],s[100010],f[65600],p[17]={1};
bool cmp(int a,int b){return a>b;}
bool vis[65600];
queue<int> q;
int n,k,x,u,i,z1,ans=0;
int chen(int x,int t,int r){
	if(r==1) return x|p[k-t];
	else return x&(~p[k-t]);
}
int erfind(int x,int m,int left,int right){
	if(left==right)return left;
	int mid=(left+right)>>1;
	if(s[mid+1]-s[x]>m) return erfind(x,m,left,mid);
	else return erfind(x,m,mid+1,right);
}
int main(){
    freopen("nochange.in","r",stdin);
    freopen("nochange.out","w",stdout);
	coin[0]=0;q.push(0);f[0]=0;
    scanf("%d%d",&k,&n); start(vis,0);
    For(1,k,i)scanf("%d",&coin[i]),coin[0]+=coin[i];
    For(1,n,i)scanf("%d",&a[i]),s[i]=a[i]+s[i-1];
    For(1,16,i)p[i]=2*p[i-1];
	sort(coin+1,coin+k+1,cmp);
	if(s[n]>coin[0]){printf("-1");return 0;}
	while(!q.empty()){
		x=q.front();q.pop();
		if(vis[x]==true)continue;
		vis[x]=true;
		if(f[x]==n){
			z1=0;
			For(1,k,i)if(!((x&p[k-i])>>(k-i)))
			z1+=coin[i];
			ans=max(ans,z1);
		}else For(1,k,i)if(((x&p[k-i])>>(k-i))==0){
			u=chen(x,i,1);
			z1=erfind(f[x],coin[i],f[x]+1,n);
			if(z1>f[u])q.push(u),f[u]=z1;
		}
	}
	cout<<ans;
    return 0;
}