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

#include<cstdio>
#include<algorithm>

using namespace std;

struct award{
  int k,p,a;
};

  award t[50];
  int s[50][50];
  int f[5000000];
  int n,m;

bool cmp1(const award x,const award y){
  return x.k<y.k;
}

int lowbit(int x){
  return x&(-x);
}

int count(int x){
  int sum=0;
  while (x){
    sum++;
    x-=lowbit(x);
  }
  return sum;
}

int award(int s,int x){
  int sum=0;
  for (int i=1;i<=m;i++){
    if (t[i].k>x){
      return sum;   
    }
    if (t[i].k==x){
      if (t[i].p<=s){
        sum+=t[i].a;
      }
    }
  }
  return sum;
}

int main(){
  freopen("deca.in","r",stdin);
  freopen("deca.out","w",stdout);
  
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++){
    scanf("%d%d%d",&t[i].k,&t[i].p,&t[i].a);
  }
  sort(t+1,t+m+1,cmp1);
  for (int i=1;i<=n;i++){
    for (int j=1;j<=n;j++){
      scanf("%d",&s[i][j]);
    }
  }
    
  int c=0;
  int now=0;
  for (int i=1;i<1 << n;i++){
    c=count(i);
    for (int j=0;j<n;j++){
      if ((i >> j)&1){
        now=(i|(1 << j))-(1 << j);
        f[i]=max(f[i],f[now]+s[j+1][c]);
      }
    }
    f[i]+=award(f[i],c);
  }
  
  printf("%d\n",f[(1 << n)-1]);
  return 0;
}