P13814 [CERC 2022] Mortgage

Andrej 是一名典型的现代学生，梦想着有一天能买上一套房子。由于买房并非易事，他正在规划自己的人生，试图弄清楚自己究竟如何以及何时能够负担得起一套房子。为了买房，他打算申请一笔按揭贷款，然后在接下来的几个月内分期偿还。对于未来的 $n$ 个月，他每个月的可用于还贷的收入为 $a_i$（其他开销已计入，因此 $a_i$ 可能为负数）。现在，他正在查看各种房产和按揭贷款，想要弄清楚自己究竟能负担得起哪些。 假设他选择了一笔按揭贷款，需要在连续的 $k$ 个月内，每个月支付 $x$ 单位的钱款，贷款从第 $i$ 个月开始，到第 $i + k - 1$ 个月结束。在这 $k$ 个月中的每一个月，他都必须能够支付 $x$ 单位的钱。如果在第 $i$ 个月他的收入有剩余，即 $a_i > x$，他可以将剩余的钱存起来，用于未来几个月的还款（第 $i + 1$ 到 $i + k - 1$ 个月同理）。然而，他不能指望在第 $i$ 个月之前存下任何钱，无论那些月份的收入是多少，他都会全部花在当前的房租和牛油果吐司上。 你将获得 Andrej 未来 $n$ 个月的收入列表，以及 $m$ 个不同的时间区间。第 $i$ 个时间区间由两个数字 $s_i$ 和 $k_i$ 定义。按揭贷款从第 $s_i$ 个月开始，持续 $k_i$ 个月，即最后一次还款在第 $s_i + k_i - 1$ 个月。对于每个时间区间，求出 Andrej 能够负担的最大每月还款额。

第一行包含两个整数 $n$ 和 $m$，分别表示月份数和时间区间数。第二行包含 $n$ 个用空格分隔的整数 $a_1, \ldots, a_n$，表示 Andrej 未来 $n$ 个月的收入。接下来 $m$ 行，每行包含两个用空格分隔的整数 $s_i$ 和 $k_i$，描述一个时间区间。

输出 $m$ 行，每行对应一个时间区间。对于第 $i$ 个按揭，输出 Andrej 能够负担的最大整数每月还款额。如果该数严格小于 $0$，则输出 “stay with parents”（不带引号）。

### 说明 对于第一个区间，Andrej 能够负担的最大每月还款额为 $4$。如果每月还款为 $5$，他将在最后一次还款时资金不足。第 $6$ 个月的负收入意味着无论贷款额度如何，Andrej 都无法负担第 $4$ 个区间的任何按揭。 ### 输入范围 - $1 \leq n, m \leq 2 \times 10^5$ - $-10^9 \leq a_i \leq 10^9$ - $1 \leq s_i \leq n; \forall i$ - $1 \leq k_i$ 且 $s_i + k_i - 1 \leq n; \forall i$ 由 ChatGPT 4.1 翻译