[USACO22OPEN] Apple Catching G

Luogu

IDLGP8272

Time2000ms

Memory256MB

DifficultyP5

贪心USACO2022排序

天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？ ## Input 输入的第一行包含 $N$（$1\le N\le 2\cdot 10^5$），为苹果落到数轴上的次数或 FJ 的奶牛出现的次数。以下 $N$ 行每行包含四个整数 $q_i$，$t_i$，$x_i$ 和 $n_i$（$q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$）。 - 如果 $q_i=1$，意味着 FJ 的 $n_i$ 头奶牛在 $t_i$ 时刻来到数轴上的 $x_i$ 位置。 - 如果 $q_i=2$，意味着 $n_i$ 个苹果在 $t_i$ 时刻落到了数轴上的 $x_i$ 位置。输入保证所有有序对 $(t_i,x_i)$ 各不相同。 ## Output 输出 FJ 的奶牛总计能接住的苹果的最大数量。 [samples] ## Note 【样例解释 1】在这个例子中，在 $t=5$ 时刻落地的 $100$ 个苹果均不能被接住。以下是一种接住 $10$ 个苹果的方式： - FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。 - FJ 的一头 $t=2$ 时刻到达的奶牛接一个 $t=8$ 时刻落地的苹果。 - 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。【样例解释 2】再一次地，在 $t=5$ 时刻落地的苹果均不能被接住。除此之外，在 $t=2$ 时刻到达的奶牛均不能接住 $t=8$ 时刻落地的苹果。以下是一种接住 $9$ 个苹果的方式： - FJ 的所有六头 $t=4$ 时刻到达的奶牛各接一个 $t=8$ 时刻落地的苹果。 - 余下三头 $t=2$ 时刻到达的奶牛各接一个 $t=6$ 时刻落地的苹果。

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO22OPEN] Apple Catching G",
    "description": {
      "content": "天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。 如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。 如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8272"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。\n\n如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会接住苹果。每头奶牛每秒可以移动一单位距离。一旦一头奶牛接住了一个苹果，她就会离开数轴。\n\n如果 FJ 的奶牛以最优方式合作，她们总共能接住多少个苹果？\n\n## Input...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments