TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3737
  • 题目
  • P3737糖果
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

       有N颗糖果(编号1到N)分给M个小孩(编号1到M),现在已知每个孩子的喜好表like[ ][ ]。如果like[i][j]==1说明第i号小孩喜欢吃第j号糖果,否则表示他不喜欢j号糖果。
       对于每个小孩,如果分到一颗喜欢的糖果,他将得到的快乐值为K。如果分一颗不喜欢的糖果,他将得到的快乐之值为1 。
       现在已知每个小孩期望得到的快乐值,第i个小孩的期望的快乐值之为Bi。如果i小孩的快乐值>=Bi,他会很高兴,否则他会很郁闷。
       问能否找到一种分配方案,使得所有小孩都很高兴。如果能输出YES,否则NO。

    输入格式

    有三组测试数据,每组测试数据格式如下:

    第一行,三个整数N,M和K (1<=N<=13, 1<=M<=13, 2<=K<=10)
    第二行,M个空格间隔的整数,其中第i个数表示i号小孩期望的快乐值Bi
    接下来一个M*N的矩阵,表示喜好表like[ ][ ]

    输出格式

    三行,每行对应一组数据,能输出YES,否则输出NO

    样例输入

    3 2 2
    2 2
    0 0 0
    0 0 1
    3 2 2
    2 2
    0 0 0
    0 0 0
    13 4 2
    4 4 8 5 
    0 1 1 1 1 1 0 0 1 0 0 0 0 
    0 0 1 0 1 0 1 1 0 0 0 0 0 
    0 1 1 1 0 0 1 1 0 0 0 1 0
    1 1 0 1 0 1 1 0 1 0 0 0 0

    样例输出

    YES
    NO
    YES