# Gemini 3.0 import sys # Increase recursion depth just in case, though not used sys.setrecursionlimit(2000) def solve(): # Read all input from stdin input = sys.stdin.read().split() if not input: return iterator = iter(input) try: n = int(next(iterator)) a = [] for _ in range(n): a.append(int(next(iterator))) b = [] for _ in range(n): b.append(int(next(iterator))) c = [] for _ in range(n): c.append(int(next(iterator))) d = [] for _ in range(n): d.append(int(next(iterator))) except StopIteration: return # Verify totals match (Constraint from problem, but good sanity check) sum_a = sum(a) sum_b = sum(b) sum_c = sum(c) sum_d = sum(d) if sum_a != sum_c or sum_b != sum_d: print("No") return # Create Source and Target structures # We need to track original indices for the subset condition. # Stores: (apple, banana, total_vol, original_index) sources = [] for i in range(n): sources.append({ 'a': a[i], 'b': b[i], 'vol': a[i] + b[i], 'id': i }) targets = [] for i in range(n): targets.append({ 'a': c[i], 'b': d[i], 'vol': c[i] + d[i], 'id': i }) # Sort by concentration of apple (a / vol) ascending. # Comparison: a1/v1 < a2/v2 <=> a1*v2 < a2*v1 from functools import cmp_to_key def compare_conc(item1, item2): # a1 * (a2+b2) - a2 * (a1+b1) # Simplify: a1/v1 vs a2/v2 -> a1*v2 vs a2*v1 val1 = item1['a'] * item2['vol'] val2 = item2['a'] * item1['vol'] if val1 < val2: return -1 elif val1 > val2: return 1 else: return 0 sources.sort(key=cmp_to_key(compare_conc)) targets.sort(key=cmp_to_key(compare_conc)) # 1. Majorization Check (Lorenz Curve) # Supply curve must be <= Demand curve (because Supply is sorted ascending, it's the 'most convex' boundary) # We check at all breakpoints of both Supply and Demand. # Collect all relevant volume checkpoints checkpoints = set() checkpoints.add(0) curr_v = 0 for s in sources: curr_v += s['vol'] checkpoints.add(curr_v) curr_v = 0 for t in targets: curr_v += t['vol'] checkpoints.add(curr_v) sorted_checkpoints = sorted(list(checkpoints)) # Helper to compute accumulated apple at volume V for a sorted list of glasses def get_acc_apple(glasses, query_vol): apple_sum = 0 current_vol = 0 for g in glasses: if current_vol >= query_vol: break remaining_needed = query_vol - current_vol take_vol = min(remaining_needed, g['vol']) # Add apple amount: take_vol * (g['a'] / g['vol']) # We work with numerators to avoid float issues? # But we need to return a value for comparison. # Since we compare SumA_supply vs SumA_demand, let's keep it precise. # We can return a fraction (numerator, denominator) or just use Python's large ints? # Python floats (64-bit) might lose precision for 10^17 * 10^17. # Let's return (numerator, denominator). Denominator is product of volumes? No, that grows too big. # We can simply accumulate the raw value as a fraction class or decimal? # Or better: We compare Sum1 vs Sum2. # Sum1 = IntPart + FracPart. # Actually, query_vol is always an integer (sum of inputs). # take_vol is integer. # g['a'] / g['vol'] is rational. # We can simply perform the calculation using fractions. term_num = take_vol * g['a'] term_den = g['vol'] # apple_sum += term_num / term_den # To avoid creating huge common denominators, maybe keep as list of fractions? # No, N=50. We can use Fraction class. current_vol += take_vol # Optimization: if taking full glass if take_vol == g['vol']: apple_sum += g['a'] # Integer addition else: # Partial from fractions import Fraction apple_sum += Fraction(term_num, term_den) return apple_sum # Perform checks # Optimization: We can iterate through checkpoints and update sums incrementally. # This avoids O(N^2) Fraction operations. src_idx = 0 src_part_vol = 0 # How much of current source glass is used src_acc_apple = 0 tgt_idx = 0 tgt_part_vol = 0 tgt_acc_apple = 0 # To handle the "fraction" part, we can keep acc_apple as Fraction from fractions import Fraction # Reset pointers for the loop prev_v = 0 for v in sorted_checkpoints: if v == 0: continue delta = v - prev_v prev_v = v # Advance Source needed = delta while needed > 0 and src_idx < n: available = sources[src_idx]['vol'] - src_part_vol take = min(needed, available) # Add apple term = Fraction(take * sources[src_idx]['a'], sources[src_idx]['vol']) src_acc_apple += term src_part_vol += take needed -= take if src_part_vol == sources[src_idx]['vol']: src_idx += 1 src_part_vol = 0 # Advance Target needed = delta while needed > 0 and tgt_idx < n: available = targets[tgt_idx]['vol'] - tgt_part_vol take = min(needed, available) term = Fraction(take * targets[tgt_idx]['a'], targets[tgt_idx]['vol']) tgt_acc_apple += term tgt_part_vol += take needed -= take if tgt_part_vol == targets[tgt_idx]['vol']: tgt_idx += 1 tgt_part_vol = 0 # Check Condition: Supply <= Demand if src_acc_apple > tgt_acc_apple: print("No") return # 2. Subset Condition Check for Min and Max concentrations # Due to the inability to swap contents without mixing, extreme concentration liquids # must stay in their original containers (or move to containers that already have that concentration). # Thus, the set of glasses required to have Min concentration must be a subset # of the glasses initially having Min concentration. Same for Max. def check_subset(is_min_check): if is_min_check: # Check Min ref_conc_item = sources[0] # Lowest concentration source # Find all sources with this concentration src_ids = set() for s in sources: if compare_conc(s, ref_conc_item) == 0: src_ids.add(s['id']) else: # Since sorted, we can break early? # Yes, sources are sorted ascending. break # Find all targets with this concentration # Note: If target asks for strictly LOWER concentration than source min, # Majorization check would have failed. # So we only care if target conc == source min conc. tgt_ids = set() for t in targets: if compare_conc(t, ref_conc_item) == 0: tgt_ids.add(t['id']) elif compare_conc(t, ref_conc_item) < 0: # Should have been caught by majorization, but for completeness: # Impossible to create lower conc. return False return tgt_ids.issubset(src_ids) else: # Check Max ref_conc_item = sources[-1] # Highest concentration source src_ids = set() # Iterate backwards for i in range(n-1, -1, -1): s = sources[i] if compare_conc(s, ref_conc_item) == 0: src_ids.add(s['id']) else: break tgt_ids = set() for t in targets: if compare_conc(t, ref_conc_item) == 0: tgt_ids.add(t['id']) elif compare_conc(t, ref_conc_item) > 0: return False return tgt_ids.issubset(src_ids) if not check_subset(True): print("No") return if not check_subset(False): print("No") return print("Yes") if __name__ == '__main__': solve()