#P18898. [2026多校联测]提前开门

[2026多校联测]提前开门

题目描述

月背小镇的夜市使用一个公用钱箱,为各摊位支付营业前的准备费用,并收取营业后的返还款。管理员阿圆需要安排摊位的营业顺序,使夜市所需的初始资金尽可能少。

夜市有 nn 个摊位,原定依次安排编号 1,2,…,n1,2,\ldots,n 的摊位营业。安排第 ii 个摊位时,必须先从公用钱箱中支付 cic_i 枚月币;随后,这个摊位完成营业,立即向钱箱返还 rir_i 枚月币,再安排下一个摊位。支付前,钱箱中的月币数必须不少于本次支付额。返还的月币可以用于之后的摊位。

在任何摊位开始营业前,阿圆可以至多修改一次原定顺序:选择一个编号 ii,其中 2≤i≤n2\le i\le n,把第 ii 个摊位移到最前面,其余摊位仍保持原来的相对顺序。也可以完全不修改顺序。

钱箱最初的月币数必须是非负整数。请确定最少需要多少枚月币,才能选取一种允许的顺序,让全部摊位完成营业;并求出以这个最低初始金额能够完成营业的不同顺序数量。

不修改顺序算一种安排;选择不同的 ii 算不同的安排。即使两个摊位的支付额、返还额相同,它们仍是不同的摊位。

输入格式

第一行一个整数 nn。

接下来 nn 行,第 ii 行两个整数 ci,ric_i,r_i,分别表示第 ii 个摊位的支付额和返还额。

输出格式

输出一行两个整数,依次为最低初始金额和达到该金额的安排数量。两个答案均不取模。

样例 1 输入

3
8 3
2 12
9 0

样例 1 输出

4 1

样例 1 解释

不修改时至少需要 88 枚月币。把 22 号摊位提前后,顺序为 2,1,32,1,3:从 44 枚月币出发,三次支付前的钱箱余额依次为 4,14,94,14,9,均足够支付;只带 33 枚则最后只剩 88 枚,不够支付 99 枚。把 33 号摊位提前至少需要 1717 枚。因此答案为 4 14\ 1。

样例 2 输入

4
0 0
0 0
7 0
7 20

样例 2 输出

7 1

样例 2 解释

把 44 号摊位提前后,从 77 枚月币出发,支付 77 枚后收到 2020 枚,足以完成其余营业。其余三种安排都要先后支付 3,43,4 号摊位的费用,中间没有返还,至少需要 1414 枚。因此最低金额为 77,最优安排只有一种。

样例 3

见下发材料中的 opening/3.in 和 opening/3.ans。这是接近完整规模的附件,不在题面中展开。

子任务

对于所有测试数据,保证:1≤n≤2000001\le n\le 200000,0≤ci,ri≤1090\le c_i,r_i\le 10^9。

各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。

子任务 分值 额外约束
1 30 n≤30n\le30
2 n≤2000n\le2000
3 40 无额外约束