← 返回题目列表

AtCoder · arc031_4

D. 好购物者

中文机器翻译题面 查看原题

問題文

高桥君沉迷于游戏。在这个游戏中,你可以通过满足特定的物品组合来获得经验值。您将获得一份物品价格和通过组合物品可以获得的经验值的列表,因此明智地选择您购买的物品以最大化“获得的经验值÷花费的金钱”。然而,该项目 1 购买超过一种类型,1 对于每种类型 如果你只有 1 ,你将获得经验值。


入力

输入将以以下格式从标准输入给出。

N M
S1 S2 ... SN
T1 T2 ... TM
K1 A1,1 A1,2 ... A1,K1
K2 A2,1 A2,2 ... A2,K2
:
KN AN,1 AN,2 ... AN,KN
  • 1 行显示您可以获得经验值的组合数量。 N (1≦N≦100) 和项目类型数量 M (1≦M≦100) 用空格分隔。 在
  • 2 行显示您可以获得的经验值数量。 Si (1≦Si≦100) 给出。
  • 3 行显示该商品的价格。 Ti (1≦Ti≦100) 给出。
  • 4 从线 N 行显示组合中包含的可为您提供经验值的物品类型数量。 Ki (1≦Ki≦10) 代表商品编号 Ki 整数 Ai,j (1≦Ai,j≦M, Ai,j<Ai,j+1) 以空格分隔 1 逐行给出。

出力

输出“获得的经验值÷花费的金钱”的最大值。绝对误差或相对误差为10−4 或更少是可以接受的。在输出末尾添加换行符。

部分点

这个问题有 2 有两个数据集,每个数据集都设置了部分点。 满足

  • N≦10 的数据集 如果您对 1 的回答正确 50 点。 如果正确答案是满足
  • 没有附加约束的数据集 如果您对 2 的回答正确,除了上述数据集之外, 50 点。 如果正确答案是满足

入力例1

3 4
4 3 2
4 2 1 10
2 1 2
2 1 3
3 2 3 4

出力例1

1

项目 1 , 项目 当您购买 2 , 项目 当您购买 3 时,您花费的钱是 7,经验值是 4+3=7 你明白了。


入力例2

5 5
7 1 3 6 6
6 3 2 6 5
1 2
2 2 3
4 1 2 4 5
2 2 4
2 2 3

出力例2

2.8