跳到主要内容
图灵 OJTURING / ONLINE JUDGE

E. 星际补给

  • 传统题
  • 1000ms
  • 256MiB

星际补给

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个小队要在 nn 个星球之间补充燃料。星球 ii 存有 aia_i 单位燃料,飞往它需要消耗 bib_i 单位燃料,与出发地无关。每个星球的燃料只能领取一次,再次到访时不会补充。

小队起初位于星球 PP,可以直接领取 aPa_P,无需支付到达起点的费用。出发前的燃料必须足够支付本次飞行消耗,抵达后才能领取目的地燃料。可以自由选择访问顺序,也可以随时停止。

首先最大化停止时剩余的燃料。在剩余燃料最多的前提下,再最大化访问过的不同星球数量,起点也计入数量。

输入格式

第一行输入 n,Pn,P。接下来 nn 行,每行输入 ai,bia_i,b_i。

输出格式

输出两行整数:第一行为最多的剩余燃料,第二行为达到该燃料量时最多访问的不同星球数量。

数据范围

1≤P≤n≤1051\le P\le n\le10^5,ai,bi≤105a_i,b_i\le10^5。请用足够大的整数类型保存燃料。

样例 1

5 3
8 5
2 7
6 90
12 9
9 9
12
4

一轮补考

未参加
状态
已结束
规则
IOI
题目
6
开始于
2026-11-3 14:00
结束于
2026-11-3 16:00
持续时间
2 小时
主持人
参赛人数
4