2022 icpc 沈阳

2022年ACM ICPC程序设计竞赛沈阳站是一项正式赛事，比赛时长为五小时。比赛题目全为英文，并且在比赛期间可以使用纸质书籍，但禁止使用电子产品。每组由三名队员组成，只允许使用一台电脑，但可以配备各种其他设备。

题目要求输入m行数据，每行包含两个数p和q，表示第p天需要租借q辆自行车。其中，p是不同的并且满足0 <= p <= 1e9的整数，q满足0 <= q <= 3e5，总租借数量sum(q)满足sum(q) <= 3e5。要求输出一个整数，表示最小总花费。

解题思路建议先将q个p展开并进行排序，以自行车租借为单位来决策，然后再考虑动态规划（dp）。可以定义二维dp数组，dp[i][j]表示第i次租借使用第j种折扣的最小总花费。但这样的时间复杂度是n * 3e5 * log(n * 3e5)，可能过不了。因此，可以考虑使用一维dp数组，并在转移方程中体现有效期和有效次数。定义dp[i]表示前i次租借的最小总花费，则dp[sum(q)]即为所求答案。

回答完问题后，请告诉我还有哪些相关问题。谢谢！

相关问题:
1. ACM ICPC程序设计竞赛沈阳站有哪些具体的比赛规则？
2. 这个竞赛中的题目难度如何？一般需要多长时间来完成一道题目？
3. 在解决这个问题时，还有其他的解决方案吗？