记录编号	397984	评测结果	AAAAAAWAWWWWA
题目名称	[USACO Nov13] 不设找零	最终得分	61
用户昵称	mouse	是否通过	未通过
代码语言	C++	运行时间	0.150 s
提交时间	2017-04-21 13:22:52	内存使用	1.29 MiB

    //KZNS
    #include <cstdio>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int K, N;
    int coin[16];
    int F[1<<16];
    int ls[1<<16];
    int lk[16];
    int cn[1<<16];
    int V[1<<16];
    int tps;
    inline int count(int x) {
    	int ans = 0;
    	while (x) {
    		x ^= x&-x;
    		ans++;
    	}
    	return ans;
    }
    inline bool cmp(int a, int b) {
    	return cn[a] < cn[b];
    } 
    int main() {
    	freopen("nochange.in", "r", stdin);
    	freopen("nochange.out", "w", stdout);
    	scanf("%d %d", &K, &N);
    	for (int i = 0; i < K; i++)
    		scanf("%d", &coin[i]);
    	for (int i = 1; i <= N; i++) {
    		scanf("%d", &V[i]);
    		V[i] += V[i-1];
    	}
    	for (int i = 0; i < K; i++)
    		lk[i] = 1<<i;
    	tps = 1<<K;
    	for (int i = 0; i < tps; i++) {
    		ls[i] = i;
    		cn[i] = count(i);
    	}
    	sort(ls, ls+(1<<K), cmp);
    	int x;
    	int l, r, md;
    	long long ans = -1, u;
    	memset(F, -1, sizeof(F));
    	F[0] = 0;
    	for (int i = 0; i < tps; i++) {
    		x = ls[i];
    		if (F[x] < 0)
    			continue;
    		if (F[x] == N) {
    			u = 0;
    			for (int j = 0; j < K; j++)
    				if (!(x & lk[j]))
    					u += coin[j];
    			ans = max(ans, u);
    			continue;
    		}
    		for (int j = 0; j < K; j++) {
    			if (x & lk[j])
    				continue;
    			l = F[x];
    			r = N;
    			while (r - l > 1) {
    				md = (l+r)>>1;
    				if (V[md] - V[F[x]] <= coin[j])
    					l = md;
    				else
    					r = md-1;
    			}
    			if (V[r] - V[F[x]] <= coin[j])
    				l = r;
    			F[x|lk[j]] = max(F[x|lk[j]], l);
    		}
    	}
    	printf("%lld\n", ans);
    	return 0;
    }
    //UBWH