Overview

This problem asks you to sum up the rewards of projects that can be delivered within \(M\) days, then subtract the agent’s commission (\(P\)%) from that total.

Analysis

• Whether project \(i\) can be completed within \(M\) days can be determined by checking if \(D_i \leq M\).
• The answer is the remaining amount after summing the rewards of qualifying projects and subtracting the commission.
• If the total reward is \(S\), the commission is \(S \times \frac{P}{100}\), so the take-home pay is \(S \times \frac{100 - P}{100}\).
• This problem can be solved by simply scanning through all projects once, so no special algorithm is needed.

Concrete example: With \(N=3, M=5, P=20\) and projects \((D=3, V=1000), (D=7, V=2000), (D=5, V=3000)\): - Projects satisfying \(D \leq 5\) are project 1 (\(D=3\)) and project 3 (\(D=5\)) - Total reward \(S = 1000 + 3000 = 4000\) - Take-home pay \(= 4000 \times (100 - 20) / 100 = 4000 \times 80 / 100 = 3200\)

Algorithm

1. Read \(N, M, P\).
2. For each project, read \(D_i\) and \(V_i\). If \(D_i \leq M\), add \(V_i\) to the reward total total.
3. Calculate the take-home amount as total * (100 - P) / 100 (integer division in C++ automatically truncates the decimal part).
4. Output the result.

Complexity

• Time complexity: \(O(N)\) (just checking each project once)
• Space complexity: \(O(1)\) (only a variable to hold the reward total)

Implementation Notes

• Beware of overflow: Since \(V_i\) can be up to \(10^6\) and \(N\) can be up to \(2 \times 10^5\), the total reward can reach up to \(2 \times 10^{11}\). This exceeds what int (approximately \(2 \times 10^9\)) can hold, so long long must be used.

• Truncation via integer division: In C++, division between integers automatically truncates the decimal part, so the floor function is not needed to satisfy the problem’s requirements. However, this works correctly only when the dividend is non-negative (in this problem, since \(0 \leq P \leq 100\), total * (100 - P) is non-negative, so there is no issue).

• Avoid floating-point arithmetic: Using floating-point numbers for the commission calculation like total * (1.0 - P/100.0) may cause precision issues that lead to incorrect answers. It is safer to process everything using integer arithmetic only.

  Source Code

#include <iostream>
using namespace std;

int main(){
    int N, M, P;
    cin >> N >> M >> P;
    long long total = 0;
    for(int i = 0; i < N; i++){
        long long D, V;
        cin >> D >> V;
        if(D <= M) total += V;
    }
    long long ans = total * (100 - P) / 100;
    cout << ans << endl;
    return 0;
}

This editorial was generated by claude4.6opus-thinking.