记录编号	96573	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14] 奶牛的十项全能	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.687 s
提交时间	2014-04-14 11:34:22	内存使用	4.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<deque>
using namespace std;
const int SIZEN=25;
int getdig(int x,int k){return (x>>(k-1))&1;}
int changedig(int x,int k,int t){
	x&=(~(1<<(k-1)));
	return x|(t<<(k-1));
}
vector<pair<int,int> > reward[SIZEN];
int S[SIZEN][SIZEN]={0};
int N,B;
int lowbit(int x){
	return x&(-x);
}
int popcount(int x){
	int ans=0;
	while(x) ans++,x-=lowbit(x);
	return ans;
}
int F[1<<20]={0};
void work(void){
	for(int i=1;i<(1<<N);i++){
		int pos=popcount(i);
		for(int j=1;j<=N;j++){
			if(getdig(i,j)){
				F[i]=max(F[i],F[changedig(i,j,0)]+S[j][pos]);
			}
		}
		int temp=0;
		for(int j=0;j<reward[pos].size();j++){
			if(F[i]>=reward[pos][j].first) temp+=reward[pos][j].second;
		}
		F[i]+=temp;
	}
	printf("%d\n",F[(1<<N)-1]);
}
void read(void){
	scanf("%d%d",&N,&B);
	int k,p,a;
	for(int i=1;i<=B;i++){
		scanf("%d%d%d",&k,&p,&a);
		reward[k].push_back(make_pair(p,a));
	}
	for(int i=1;i<=N;i++) sort(reward[i].begin(),reward[i].end());
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) scanf("%d",&S[i][j]);
}
int main(){
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	read();
	work();
	return 0;
}