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

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>

using namespace std;

const int MAXN=20+1;

int N,B;

int s_ij[MAXN][MAXN]={0};

struct reward{
	int tot_num;
	int p_i[MAXN];
	int a_i[MAXN];
	reward(){
		tot_num=0;
	}
}k_i[MAXN];

int f[MAXN][1<<MAXN]={0};

void read(){
	scanf("%d %d",&N,&B);
	for(int i=1;i<=B;i++){
		int k,p,a;scanf("%d %d %d",&k,&p,&a);
		k_i[k].p_i[ k_i[k].tot_num ]=p;
		k_i[k].a_i[ k_i[k].tot_num ]=a;
		k_i[k].tot_num++;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			int s;scanf("%d",&s);
			s_ij[i][j]=s;
		}
	}
}

inline int cal_tot(int s){
	int k=1,ans=0;
	for(int i=0;i<N;i++){
		if(s&k)ans++;
		k<<=1;
	}
	return ans;
}

void work(){
	read();
	for(int i=1;i<=N;i++){
		//int poj=0;
		for(int s=1<<(i-1);s<(1<<N);s++){
			
			int tot_cow=cal_tot(s);
			if(tot_cow!=i)continue;
			//poj++;
			int ans=0;
			
			int cow=0;
			for(int k=1;k<(1<<N);k<<=1){
				cow++;
				if(!(s&k))continue;
				int temp=0;
				temp=f[i-1][s^k]+s_ij[cow][i];
				
				reward & re=k_i[i];
				int reward_num=0;
				for(int r=0;r<re.tot_num;r++){
					if(temp>=re.p_i[r]){
						reward_num+=re.a_i[r];
					}
				}
				temp+=reward_num;
				ans=max(ans,temp);
			}
			f[i][s]=ans;
		}
	}
	printf("%d\n",f[N][(1<<N)-1]);
}

void test(){
	N=13;
	cout<<cal_tot(14243);
}

void open(){
	//freopen("in.txt","r",stdin);
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
}

int main(){
	open();
	work();
	//test();
	
	return 0;
}