Overview

This problem asks you to determine whether all debts can be fully repaid by computing the “deadline turn” by which each debt must be repaid before it grows too large due to interest, and then applying a greedy algorithm (Earliest Deadline First) that prioritizes repaying debts with the most imminent deadlines.

Analysis

1. Organizing the Conditions for Full Repayment

Let us number the turns starting from turn \(0\), then turn \(1\), and so on. At the repayment phase of turn \(t\), the balance of debt \(i\) is the initial balance \(H_i\) plus \(t\) rounds of interest \(G_i\), i.e., \(H_i + t \cdot G_i\) yen.

To fully repay debt \(i\) at turn \(t\), the balance at that point must be at most \(P\). $\(H_i + t \cdot G_i \leq P\)$

Solving this inequality for \(t\), we get: $\(t \cdot G_i \leq P - H_i\)\( \)\(t \leq \left\lfloor \frac{P - H_i}{G_i} \right\rfloor\)$

(Here, \(\lfloor x \rfloor\) denotes the largest integer not exceeding \(x\).)

In other words, debt \(i\) can be fully repaid no later than turn \(R_i = \left\lfloor \frac{P - H_i}{G_i} \right\rfloor\). If \(H_i > P\) from the start, the debt cannot be repaid even at turn \(0\), so full repayment is impossible.

2. Reduction to a Scheduling Problem

There are \(N\) debts in total, and at most \(1\) debt can be fully repaid per turn. Therefore, to repay all debts, all repayments must be completed by turn \(N-1\) at the latest.

Thus, the effective deadline \(D_i\) for each debt \(i\) can be defined as the smaller of \(R_i\) and \(N-1\): $\(D_i = \min\left( \left\lfloor \frac{P - H_i}{G_i} \right\rfloor, N - 1 \right)\)$

The problem reduces to the following task scheduling problem: “Each debt \(i\) must be repaid by turn \(D_i\). If only one debt can be repaid per turn, can all debts be repaid within their deadlines?”

3. Applying the Greedy Algorithm

For processing tasks with deadlines like this, the greedy strategy “process the task with the most imminent deadline (smallest \(D_i\)) first” is optimal.

Intuitively, if you postpone a debt with little slack and repay a debt with more slack first, the debt with little slack will expire (exceed \(P\) and become impossible to repay). Therefore, prioritizing the ones closest to their deadline is the best strategy.

Specifically, compute the deadline \(D_i\) for each debt and sort them in ascending order. Let the sorted array of deadlines be \(D'_0, D'_1, \dots, D'_{N-1}\). The deadline \(D'_j\) of the debt repaid \(j\)-th (\(0 \leq j < N\)) must be at least the turn \(j\) at which it is actually repaid.

That is, if the following holds for all \(j\), output Yes; if even one fails, output No: $\(D'_j \geq j\)$

Algorithm

1. For each debt \(i\) (\(0 \leq i < N\)), do the following:
   • If \(H_i > P\), immediately output No and terminate.
   • Otherwise, compute the deadline \(D_i = \min\left( \lfloor \frac{P - H_i}{G_i} \rfloor, N - 1 \right)\) and store it in array \(D\).
2. Sort array \(D\) in ascending order.
3. For \(j = 0, 1, \dots, N-1\), check whether there exists a \(j\) such that \(D[j] < j\).
   • If such a \(j\) exists, there is a debt that cannot be repaid within its deadline, so output No and terminate.
4. If the condition is satisfied for all \(j\), output Yes.

Complexity

• Time Complexity: \(O(N \log N)\) Computing the deadline for each debt takes \(O(N)\), sorting the deadline array takes \(O(N \log N)\), and the final verification takes \(O(N)\). The overall bottleneck is the sorting step, which runs sufficiently fast for the constraint \(N \leq 2 \times 10^5\).

• Space Complexity: \(O(N)\) We use an array D of size \(N\) to store the deadline for each debt.

Implementation Notes

• Integer Division (Floor): In C++, (P - H) / G automatically returns the integer with the fractional part truncated (floor function) when operating on positive integers, so it can be used as-is without issues.

• Avoiding Overflow: Since \(P, H_i, G_i\) can be up to \(10^9\), we use long long types to prevent overflow during computation.

• Capping the Deadline: \(R_i\) can become very large, but since all debts must be repaid by turn \(N-1\) at the latest, we use min(R, N - 1) to cap the value at \(N-1\). This avoids handling unnecessarily large numbers and allows safe comparisons.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long P;
    if (!(cin >> N >> P)) return 0;

    vector<long long> D(N);
    for (int i = 0; i < N; ++i) {
        long long H, G;
        cin >> H >> G;
        if (H > P) {
            cout << "No\n";
            return 0;
        }
        long long R = (P - H) / G;
        D[i] = min(R, (long long)N - 1);
    }

    sort(D.begin(), D.end());

    for (int j = 0; j < N; ++j) {
        if (D[j] < j) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.