#P18898. [2026多校联测]提前开门
[2026多校联测]提前开门
题目描述
月背小镇的夜市使用一个公用钱箱,为各摊位支付营业前的准备费用,并收取营业后的返还款。管理员阿圆需要安排摊位的营业顺序,使夜市所需的初始资金尽可能少。
夜市有 个摊位,原定依次安排编号 的摊位营业。安排第 个摊位时,必须先从公用钱箱中支付 枚月币;随后,这个摊位完成营业,立即向钱箱返还 枚月币,再安排下一个摊位。支付前,钱箱中的月币数必须不少于本次支付额。返还的月币可以用于之后的摊位。
在任何摊位开始营业前,阿圆可以至多修改一次原定顺序:选择一个编号 ,其中 ,把第 个摊位移到最前面,其余摊位仍保持原来的相对顺序。也可以完全不修改顺序。
钱箱最初的月币数必须是非负整数。请确定最少需要多少枚月币,才能选取一种允许的顺序,让全部摊位完成营业;并求出以这个最低初始金额能够完成营业的不同顺序数量。
不修改顺序算一种安排;选择不同的 算不同的安排。即使两个摊位的支付额、返还额相同,它们仍是不同的摊位。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 ,分别表示第 个摊位的支付额和返还额。
输出格式
输出一行两个整数,依次为最低初始金额和达到该金额的安排数量。两个答案均不取模。
样例 1 输入
3
8 3
2 12
9 0
样例 1 输出
4 1
样例 1 解释
不修改时至少需要 枚月币。把 号摊位提前后,顺序为 :从 枚月币出发,三次支付前的钱箱余额依次为 ,均足够支付;只带 枚则最后只剩 枚,不够支付 枚。把 号摊位提前至少需要 枚。因此答案为 。
样例 2 输入
4
0 0
0 0
7 0
7 20
样例 2 输出
7 1
样例 2 解释
把 号摊位提前后,从 枚月币出发,支付 枚后收到 枚,足以完成其余营业。其余三种安排都要先后支付 号摊位的费用,中间没有返还,至少需要 枚。因此最低金额为 ,最优安排只有一种。
样例 3
见下发材料中的 opening/3.in 和 opening/3.ans。这是接近完整规模的附件,不在题面中展开。
子任务
对于所有测试数据,保证:,。
各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 30 | |
| 2 | ||
| 3 | 40 | 无额外约束 |