[SEERC 2020] Neo-Robin Hood

Luogu

IDLGP10747

Time4000ms

Memory256MB

DifficultyP6

2020ICPCSEERC

你是一个大盗，镇上一共有 $n$ 户人家，对于每户人家 $i$，你在如下的选择里选一样。 - 盗窃他的 $m_i$ 元钱，他会对你起仇恨。 - 给他 $p_i$ 元钱，他会让你盗窃的一个人取消对你的仇恨。 - 什么也不做。初始时你没有钱，你想知道，在没人对你有仇恨且你手中的钱非负的情况下，你最多能盗窃多少户人家。注：你可以按任意顺序依次访问每户人家。 ## Input 第一行一个整数 $n\ (1 \leq n \leq 10^5)$。第二行一个长度为 $n$ 的序列 $m\ (1 \leq m_i \leq 10^9)$。第三行一个长度为 $n$ 的序列 $p\ (1 \leq p_i \leq 10^9)$。 ## Output 输出最多能盗窃的人家数。 [samples]

Samples

Input #1

5
2 3 4 5 6
1 2 3 4 5

Output #1

Input #2

4
1 2 4 2
5 6 9 7

Output #2

Input #3

4
9 19 6 5
20 3 16 19

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[SEERC 2020] Neo-Robin Hood",
    "description": {
      "content": "你是一个大盗，镇上一共有 $n$ 户人家，对于每户人家 $i$，你在如下的选择里选一样。 - 盗窃他的 $m_i$ 元钱，他会对你起仇恨。 - 给他 $p_i$ 元钱，他会让你盗窃的一个人取消对你的仇恨。 - 什么也不做。 初始时你没有钱，你想知道，在没人对你有仇恨且你手中的钱非负的情况下，你最多能盗窃多少户人家。 注：你可以按任意顺序依次访问每户人家。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10747"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你是一个大盗，镇上一共有 $n$ 户人家，对于每户人家 $i$，你在如下的选择里选一样。\n\n- 盗窃他的 $m_i$ 元钱，他会对你起仇恨。\n\n- 给他 $p_i$ 元钱，他会让你盗窃的一个人取消对你的仇恨。\n\n- 什么也不做。\n\n初始时你没有钱，你想知道，在没人对你有仇恨且你手中的钱非负的情况下，你最多能盗窃多少户人家。\n\n注：你可以按任意顺序依次访问每户人家。\n\n## Input\n\n第一行一个...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments