TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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


    ソース  2012 Multi-University Training Contest 3