[BalticOI 2024] Jobs

Luogu
IDLGP10759
Time1000ms
Memory250MB
DifficultyP6
贪心2024可并堆BalticOI(波罗的海)启发式合并
目前,你可以选择从 $1$ 到 $N$ 编号的 $N$ 个一次性工作。 完成第 $i$ 个工作将给你带来 $x$ 欧元的利润,当然,利润也可能是负的。 有些工作依赖于另一个工作。也就是说,可能有一个编号为 $p$ 的工作必须在第 $i$ 个工作开始之前完成。因此,一个利润较大的工作如果依赖于一个利润为负的工作,看起来收益可能会比较小。 如果 $p = 0$,则第 $i$ 个工作没有依赖。 你目前有 $s$ 欧元,可以决定做哪些工作以及以什么顺序去做,只要尊重依赖关系。此外,你所拥有的钱数在任何时候都不能变成负数。 请计算通过选择按照某种顺序完成(也可能某些选择不完成)这 $N$ 个工作所能获得的最大利润。 ## Input 第一行包含两个整数 $N$ 和 $s$,分别是工作的数量和你最初拥有的金额。 接下来的 $N$ 行,每行包含两个整数 $x$ 和 $p$,分别是第 $i$ 个工作的利润和它所依赖的前置工作的编号。如果 $p = 0$,则第 $i$ 个工作没有依赖。 ## Output 你的程序应该输出一个整数,即你能够获得的最大利润。 [samples] ## Background 翻译自 [BalticOI 2024 Day1 T1](https://boi2024.lmio.lt/tasks/d1-jobs-statement.pdf)。 ## Note 分别选择 $1,4,3,5$ 号工作即可,总利润为 $3+2-5+6 = 6$。 | 子任务编号 | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | | $1$ | $s = 10^{18}$ | $11$ | | $2$ | $N \leq 2000$ 且满足性质 A | $14$ | | $3$ | 满足性质 A | $15$ | | $4$ | $N \leq 2000$ | $29$ | | $5$ | 无特殊性质 | $31$ | * 性质 A:每个 $p_i$ 要么是 $0$,要么是 $i-1$。 对于所有的数据,$1 \leq N \leq 3 \times 10^5$,$0 \leq s \leq 10^{18}$,$-10^9 \leq x_i \leq 10^9$,$0 \leq p_i < i$。
Samples
Input #1
6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "[BalticOI 2024] Jobs",
    "description": {
      "content": "目前,你可以选择从 $1$ 到 $N$ 编号的 $N$ 个一次性工作。 完成第 $i$ 个工作将给你带来 $x$ 欧元的利润,当然,利润也可能是负的。 有些工作依赖于另一个工作。也就是说,可能有一个编号为 $p$ 的工作必须在第 $i$ 个工作开始之前完成。因此,一个利润较大的工作如果依赖于一个利润为负的工作,看起来收益可能会比较小。 如果 $p = 0$,则第 $i$ 个工作没有依赖。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 256000
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10759"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "目前,你可以选择从 $1$ 到 $N$ 编号的 $N$ 个一次性工作。\n\n完成第 $i$ 个工作将给你带来 $x$ 欧元的利润,当然,利润也可能是负的。\n\n有些工作依赖于另一个工作。也就是说,可能有一个编号为 $p$ 的工作必须在第 $i$ 个工作开始之前完成。因此,一个利润较大的工作如果依赖于一个利润为负的工作,看起来收益可能会比较小。\n\n如果 $p = 0$,则第 $i$ 个工作没有依赖。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments