题目详情题解（0）讨论（0）提交记录（0）

AT_arc031_4.[ARC031D] 買い物上手

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君沉迷于一款游戏。在这款游戏中，玩家可以通过购买并组合一些物品来获取经验值。给定每种物品的价格以及通过指定物品组合获得的经验值列表，要求你选择购买的物品，使得「获得的经验值 ÷ 花费的金钱」最大化。需要注意的是，至少购买一种物品，而且每种物品只需要购买一个就可以获得相应的经验值。

输入格式

输入以如下格式提供：

  • 第一行包含两个整数 NN 和 MM，分别表示可获得经验值的组合数和物品种类数，其中 1≤N≤1001 \le N \le 100，1≤M≤1001 \le M \le 100。
  • 第二行包含 NN 个整数，表示每个组合中可获得的经验值大小。
  • 第三行包含 MM 个整数，表示每种物品的价格。
  • 接下来的 NN 行，每行描述一个经验值组合。具体来说，每行的开头是一个整数，表示该组合中包含的物品种类数量。接着是若干整数，表示该组合所需的物品编号，编号以递增的顺序给出，并且不重复。

输出格式

输出使「获得的经验值 ÷ 花费的金钱」最大化的结果。结果的绝对误差或相对误差不超过 10−410^{-4} 即可被接受。输出结果末尾需换行。

输入输出样例

  • 输入#1

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

    输出#1

    1

  • 输入#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

说明/提示

在本问题中共有两个数据集，每个数据集的具体条件如下：

  • 如果在数据集中 N≤10N \le 10 的情况下提供正确答案，可以得到 5050 分。
  • 在没有额外限制的情况下提供正确答案，可以在前述数据集之外额外得到 5050 分。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页