Proficient.
Put your skills to the test.

Problem summary

A buyer owns m banknotes and a seller owns n banknotes. For a positive integer price at most the buyer’s total money, payment may use any buyer banknotes and change may use the banknotes then available to the seller. Find the largest price that cannot be paid exactly, or zero if every affordable integer price is possible.

Constraints

m,n ≥ 1; m+n < 1,000,000; all denominations are positive integers and their combined sum is less than 10¹⁵.

Worked example

An independently prepared example for this explanation.

2 10 1
1 2

7

Solution analysis

1. Let S be the buyer’s total. Imagine handing over every buyer banknote first. A price P is possible exactly when some subset of all banknotes totals S−P: that subset can be returned as change. This also covers payments using fewer buyer notes, since the unused notes can be included in the returned subset.
2. Therefore the largest impossible price corresponds to the smallest positive subset sum that cannot be formed. Sort all denominations. If sums from 0 through covered are possible, a note x ≤ covered+1 extends this interval through covered+x. A larger x leaves covered+1 permanently impossible, because all remaining notes are at least x.
3. For buyer notes 10 and 1 and seller note 2, the sorted notes start 1,2,10. The first two cover 0 through 3; 4 is missing. Since S = 11, the answer is 11−4 = 7. If the first missing sum is at least S, all positive prices are feasible and the answer is zero.

Why it works

Payment and a returned subset have equal net value P exactly when that subset totals S−P, proving the reduction. The interval extension rule follows by joining [0,covered] and [x,x+covered]. If x exceeds covered+1, no subset of processed notes reaches the gap and any remaining note already exceeds it. The greedy scan thus finds the smallest missing sum, and reversing S−P gives the largest impossible positive price.

Watch out. Include both people’s banknotes in the sorted list, but only the buyer’s notes in S. Use 64-bit totals. A missing change sum S corresponds to price zero and must produce answer zero.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    vector<long long>notes;
    long long buyerTotal=0;
    for(int i=0;i<count;++i){
        long long value;
        cin>>value;
        notes.push_back(value);
        buyerTotal+=value;
    }
    cin>>count;
    for(int i=0;i<count;++i){
        long long value;
        cin>>value;
        notes.push_back(value);
    }
    sort(notes.begin(),notes.end());
    long long covered=0;
    for(long long value:notes){
        if(value>covered+1){
            break;
        }
        // All sums from zero through covered remain attainable.
        covered+=value;
    }
    cout<<max(0LL,buyerTotal-covered-1)<<'\n';
}