Real problems.
Your next challenge.

Problem summary

Choose two disjoint, nonempty teams from N students; students may be left unused. Student i has skill Sᵢ and popularity Pᵢ. The teams must have equal total skill. Each captain has the greatest popularity in their team, so the interest of a match is the absolute difference between the two teams’ maximum popularities. Maximize this interest.

Constraints

1 ≤ N ≤ 500; all skills are positive; sum of skills ≤ 100,000; 1 ≤ Pᵢ ≤ 10⁹. A valid pair of teams is guaranteed.

Worked example

An independently prepared example for this explanation.

3
2 1 1
9 3 4

5

Solution analysis

1. Sort students by increasing popularity. Designate the team with the larger captain popularity as A and the other team as B.
2. For already processed students, dp[d] is the smallest possible maximum popularity of team B among assignments with skill(A)−skill(B)=d. Unused students are allowed; the empty B has cost zero. Keep all differences from −T to T, where T is total skill.
3. Before inserting a student (s,p), making that student A’s captain gives equal skills exactly when the old difference is −s. Therefore test p−dp[−s]. Then update into a fresh array: skip the student; add them to A without changing the cost; or add them to B and set the cost to p.
4. Checking before insertion prevents reusing the captain. Since s>0, a state of difference −s necessarily has a nonempty B; inserting the captain makes A nonempty too.

Why it works

Inductively the DP covers every assignment of the processed students and retains the cheapest B maximum for each difference, which dominates every more expensive state for future transitions. In any optimal solution, process one of A’s maximum-popularity students last among the selected students, swapping A and B if needed. Its candidate query considers the remaining assignment, obtaining at least the optimal interest; every candidate is itself feasible. Equal-popularity ties cause no problem because a zero-interest pair can be considered when its last selected student is inserted.

Watch out. The teams must be disjoint, not merely two independently attainable subset sums. A fresh DP layer is needed so one student cannot enter both teams.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<iterator>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>s(n),p(n);
    int T=0;
    for(int&x:s){
        cin>>x;
        T+=x;
    }
    for(int&x:p){
        cin>>x;
    }
    vector<pair<int,int>>a;
    for(int i=0;i<n;i++){
        a.push_back({p[i],s[i]});
    }
    sort(a.begin(),a.end());
    const int INF=2000000000;
    vector<int>dp(2*T+1,INF),next;
    dp[T]=0;
    int span=0,answer=0;
    for(auto[pop,skill]:a){
        if(skill<=span&&dp[T-skill]!=INF){
            answer=max(answer,pop-dp[T-skill]);
        }
        next=dp; // Separate layers forbid using this student twice.
        for(int d=-span;d<=span;d++){
            if(dp[T+d]!=INF){
                next[T+d+skill]=min(next[T+d+skill],dp[T+d]); // Join A.
                next[T+d-skill]=min(next[T+d-skill],pop); // Join B.
            }
        }
        dp.swap(next);
        span+=skill;
    }
    cout<<answer<<'\n';
}