Overview

This problem asks us to select a subset from \(N\) employees and maximize the minimum of the total programming ability and the total design ability (overall strength). The conclusion is that selecting everyone is optimal.

Analysis

Key Insight: Selecting Everyone is Always Optimal

The most important point of this problem is the constraint that all ability values are positive (\(A_i \geq 1, B_i \geq 1\)).

Consider adding an employee \(j\) who has not yet been selected to the current team \(S\):

• Total programming ability: \(\sum A_i \to \sum A_i + A_j\) (increases since \(A_j > 0\))
• Total design ability: \(\sum B_i \to \sum B_i + B_j\) (increases since \(B_j > 0\))

Since both totals increase, the smaller of the two values (= overall strength) also necessarily increases.

Concrete Example

For example, if there are 3 employees with \((A, B) = (5, 3), (2, 6), (1, 4)\):

Selected Employees	\(\sum A\)	\(\sum B\)	Overall Strength \(= \min\)
{1}	5	3	3
{1, 2}	7	9	7
{1, 2, 3}	8	13	8

We can see that the overall strength increases each time a person is added.

Why a Naive Approach is Unnecessary

There is no need to search through all \(2^N - 1\) possible subsets. From the analysis above, we can prove that selecting everyone is the only optimal choice, so we simply need to calculate the total for all employees.

Algorithm

1. Calculate the total programming ability of all employees: \(\text{sumA} = \sum_{i=1}^{N} A_i\)
2. Calculate the total design ability of all employees: \(\text{sumB} = \sum_{i=1}^{N} B_i\)
3. Output \(\min(\text{sumA}, \text{sumB})\)

Complexity

• Time complexity: \(O(N)\) (just reading each employee’s ability values once and computing the sums)
• Space complexity: \(O(1)\) (only variables to hold the sum values)

Implementation Notes

• Since \(N\) can be up to \(2 \times 10^5\) and each ability value can be up to \(10^9\), the total can reach approximately \(2 \times 10^{14}\). int will overflow, so you need to use long long.

• The essence of the problem lies in the mathematical observation that “selecting everyone is optimal,” and the implementation itself is very simple.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long sumA = 0, sumB = 0;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        sumA += a;
        sumB += b;
    }
    cout << min(sumA, sumB) << endl;
    return 0;
}

---

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