⚙️AlgorithmAdvanced

Aliens Trick (WQS Binary Search)

Key Points

•
Aliens Trick (WQS Binary Search) converts a hard “exactly k items” optimization into an unconstrained problem by adding a penalty λ per chosen item.
•
For any fixed $λ,$ solve min(cost + λ × count) quickly; the number of chosen items decreases monotonically as λ increases.
•
Binary search λ until the optimal solution chooses k items; the exact objective value is recovered by subtracting/adding kλ appropriately.
•
This works when the optimal value as a function of k is discrete-convex, so the count is monotone in λ and there are no bad local minima.
•
Tie-breaking is crucial: when adjusted values are equal, prefer the solution with a larger count to preserve monotonicity for binary search.
•
After finding $λ *,$ compute the true answer as A( $λ *)$ − $λ *$ k in the “minimization + penalty” form or as B( $λ *)$ + $λ *$ k in the “maximization − penalty” form.
•
WQS is powerful for DPs that would otherwise need an extra dimension for count, as well as for MST/Kruskal-style problems with “special edge” counts.
•
Careful range selection for $λ,$ 64-bit safety, and consistent monotone decisions are essential for correct and stable implementations.

Prerequisites

→Minimum Spanning Tree (Kruskal/Prim) — To understand how adjusted weights affect edge selection and why Kruskal still yields optimal trees under linear weight shifts.
→Dynamic Programming basics — Penalized subproblems are typically solved with DP; understanding states, transitions, and tie-breaking is essential.
→Discrete convexity and monotonicity — WQS relies on monotone counts and convexity to ensure binary search correctness.
→Binary Search — WQS is a binary search over λ; one must maintain correct invariants and stopping conditions.
→Greedy Choice / Exchange Arguments — To justify monotonicity and the validity of reweighted greedy algorithms like Kruskal with λ shifts.
→Disjoint Set Union (Union-Find) — Needed for fast MST construction with Kruskal in the MST example.
→Asymptotic Analysis — To analyze O(n log R) style complexities and understand the trade-offs of outer search times.
→Fenchel-Legendre Transform (conceptual) — Gives the theoretical backdrop linking A(λ) and F(k) and explains why subtracting/adding λk recovers the true value.

Detailed Explanation

Tap terms for definitions

01Overview

Aliens Trick, also called Weighted Quick Search (WQS) binary search, is a parametric optimization technique that solves problems of the form “optimize cost subject to selecting exactly k items.” Instead of handling the hard cardinality constraint directly, we assign a penalty λ to each selected item and solve an easier, unconstrained problem: minimize cost + λ × count (or maximize value − λ × count). For each λ, this reduced problem is often solvable with a simpler dynamic programming (DP), greedy, or graph algorithm. As λ increases, selecting items becomes more expensive, so the optimal solution uses fewer items. This monotone relationship allows us to binary search on λ to find a solution that uses exactly k items. The magic is that the function F(k) = optimal value with exactly k items is discrete-convex in many common settings (interval scheduling, non-overlapping subarrays, MST with special edges). Discrete convexity implies the set of optimal counts as λ varies drops monotonically. After we find λ*, the unconstrained solution at λ* yields an adjusted objective A(λ*) = min(cost + λ* × count). The true constrained optimum for exactly k items is then A(λ*) − λ* k (or its maximization counterpart). This trick removes the need for an explicit O(nk) DP, replacing it with O(n log Range) by binary searching λ and running the fast solver each time.

02Intuition & Analogies

Imagine you’re buying apples, but you must end up with exactly k apples, and each apple has a different price and some extra “hassle” cost that makes choosing subsets complicated. Handling the “exactly k” rule directly is awkward: you either buy too few or too many and must keep juggling. Aliens Trick says: instead of forcing exactly k apples, pretend every apple also has a tax λ. If λ is cheap, you’ll happily buy many apples; if λ is huge, you’ll avoid them. By tuning λ, you can nudge yourself into buying exactly k apples without ever coding special logic for the count. Think of λ as a knob. Turn it down, and your solution includes more items; turn it up, and it drops items. Because the number of items changes predictably with λ (monotone), you can do a simple warmer/colder game (binary search) to land on the λ that just yields k. That’s the search part. Now, since you artificially injected λ into the price tags, the total you computed includes fake money. To get the real bill, you simply subtract k times λ (if you were minimizing with a +λ penalty) or add k times λ (if you were maximizing with a −λ penalty). The idea is like adding and then later removing a uniform surcharge to control quantity without complicating your selection algorithm. This is powerful when the unconstrained version with a per-item linear adjustment becomes a clean DP or a greedy algorithm, such as Kruskal’s MST or interval DP. You outsource the hard counting constraint to a single parameter and a binary search, while the solver remains simple and fast.

03Formal Definition

Let X be the set of feasible solutions, cost(x) the objective, and cnt(x) the number of selected items. Define the k-restricted value F(k) =

min

\{ cost(x) : x

\in

X,\ cnt(x) = k \}. Suppose F(k) is discrete-convex: the forward differences

Δ

F(k) = F(k+1) − F(k) form a nondecreasing sequence. For any

λ

\in

R

, define the penalized problem value A(

λ

) =

min_{x \in X}

\big

( cost(x) +

λ

\, cnt(x)

\big

). Then A(

λ

) is the Legendre-Fenchel transform (up to sign) of F: A(

λ

) =

min_{k}

\big

( F(k) +

λ

\big

). Conversely, F(k) =

max_{λ}

\big

( A(

λ

) -

λ

\big

). In many combinatorial problems with linear cardinality cost, A(

λ

) is efficiently computable with greedy or DP. Let

x_{λ}

be an optimizer of A(

λ

), and let c(

λ

) = cnt(

x_{λ}

). Under discrete convexity, c(

λ

) is a nonincreasing function of

λ

(a subgradient selection). Therefore, we can binary search

λ

to find

λ^{*}

such that c(

λ^{*}

)

\geq

k and c(

λ^{*}

ϵ

)

\leq

k for arbitrarily small

ϵ

> 0. Then F(k) = A(

λ^{*}

) -

λ^{*}

k. For maximization forms with penalty −

λ

per item, analogous relations hold: define B(

λ

) =

max_{x}

\big

( value(x) -

λ

\, cnt(x)

\big

), and recover the exact-k value as B(

λ^{*}

) +

λ^{*}

04When to Use

Use Aliens Trick when your problem has a linear cost in the number of chosen items and the unconstrained penalized problem becomes easy. Classic scenarios include: (1) Dynamic programs where adding a count dimension would make it O(nk), but the count can be traded for a single scalar λ and solved in O(n); examples: picking exactly k non-overlapping subarrays with maximum sum or choosing exactly k weighted, non-overlapping intervals. (2) Greedy structures where a linear shift in edge/item weights preserves greedy optimality; example: an MST where each “special” edge has an added λ; Kruskal’s algorithm still applies and the number of special edges in the MST is monotone in λ. (3) Problems where the exact-k objective value as a function of k is discrete-convex (or at least where the selected count in the penalized optimum is monotone in λ). If you can prove or strongly argue this monotonicity (by exchange arguments or matroid/convex DP structure), WQS is a strong candidate. Avoid it if the count is not monotone in λ (e.g., highly nonconvex selection interactions), or if your solver for a fixed λ is itself expensive (then the outer binary search multiplies cost). It also may be unsuitable when λ must be searched over a massive continuous range without integrality or when precision issues complicate stopping conditions.

⚠️Common Mistakes

Forgetting to recover the true objective: After solving the penalized problem, you must undo the penalty. For minimization with +\lambda per item, return A(\lambda) − \lambda k; for maximization with −\lambda per item, return B(\lambda) + \lambda k.
Wrong tie-breaking: When two penalized solutions have equal adjusted value, choose the one with the larger count. This ensures the count c(\lambda) is the maximal one at that \lambda and stays monotone as \lambda increases, stabilizing the binary search.
Insufficient \lambda range: Pick bounds so that at the low end you certainly select many items (c(\lambda_{low}) \ge k) and at the high end you select few or none (c(\lambda_{high}) \le k). If not, the search may never bracket k.
Overflow and precision: Use 64-bit integers for values and penalties, and consider long double when sums can exceed 64-bit. Keep the number of binary search iterations bounded and prefer integer \lambda when inputs are integers.
Misinterpreting inequalities in the search: For minimization with +\lambda per item, if c(\lambda) \ge k, increase \lambda (to reduce count); if c(\lambda) < k, decrease \lambda. Maintain a correct invariant (e.g., the largest \lambda with c(\lambda) \ge k).
Assuming exact c(\lambda) = k is necessary: You can compute F(k) via A(\lambda^{}) − \lambda^{} k at the bracketing \lambda^{}, even if the optimizer has c(\lambda^{}) \ne k, provided discrete convexity holds.

Key Formulas

Exact-k objective

F (k) = x \in X, c n t (x) = k min cost (x)

Explanation: F(k) is the optimal value when exactly k items are chosen. Our goal is to compute this without explicitly iterating over k in the DP.

Penalized minimization

A (λ) = x \in X min (cost (x) + λ cnt (x))

Explanation: For a fixed penalty λ per item, solve the unconstrained problem. This is usually easy via DP or greedy.

Conjugacy relation

A (λ) = k \geq 0 min (F (k) + λk)

Explanation: The penalized value is the minimum over k of the exact-k value plus $λk .$ This connects the unconstrained and constrained problems.

Recover exact-k

F (k) = λ \in R max (A (λ) - λk)

Explanation: Once we have A( $λ),$ we can get the exact-k value by subtracting $λk$ and maximizing over $λ .$ In practice, binary search finds a suitable $λ .$

Slope-count connection

\frac{d}{d λ ^{+}} A (λ) = c (λ) (right slope), monotone nonincreasing

Explanation: The slope of A( $λ)$ equals the selected count (up to sign convention). As λ increases, the optimal count does not increase.

MST edge adjustment

w_{e}^{'} = w_{e} + λ s_{e}

Explanation: Add λ to each special edge weight. Kruskal on w' chooses fewer special edges as λ grows.

Interval DP with penalty

DP_{i} = max (DP_{i - 1}, DP_{p (i)} + w_{i} - λ)

Explanation: Classic weighted interval scheduling DP where choosing interval i pays its weight minus $λ;$ p(i) is the last compatible interval.

Maximization form

B (λ) = x max (value (x) - λ cnt (x)), answer (k) = B (λ^{*}) + λ^{*} k

Explanation: For maximization, subtract λ per item, then add back $λk$ at the end to get the exact-k value.

Search complexity

O (n lo g R)

Explanation: Binary search over λ does O(log R) iterations, each solving a size-n subproblem. R is the λ search range or precision domain.

Complexity Analysis

Let T(

λ)

be the time to solve the penalized subproblem for a given

λ .

WQS binary search typically performs O(log R) iterations, where R is the range or precision for

λ .

With integer inputs and linear penalties, λ can be searched over an integer range that safely brackets the target count k; this yields total time O(T · log R). For DP-based solvers (intervals or non-overlapping subarrays),

T = O (n

) or O(n log n) depending on preprocessing (like computing predecessors with binary search). For graph problems like MST with Kruskal’s algorithm,

T = O (m

log m) per iteration due to sorting; with the sort fixed and only weights adjusted, T can be reduced by reusing the sorted order if λ affects only tie-breaking predictably, but typically we just sort once by w' each iteration, so O(m log m log R). Space complexity is usually the same as the underlying solver: O(n) for linear-time DPs, O(n) for interval DPs after sorting, and O(m) for MST (plus DSU structures). The binary search adds only O(1) extra memory. The constants are small, but beware that increasing λ range inflates the number of iterations; with 60 iterations on 64-bit ranges, runtimes remain practical when T is near-linear. Numerical stability: for integer weights and counts, use 64-bit integers (long long) for λ and objective values. When values may exceed 64 bits, consider built-in big integers (rare in C++) or long double for temporary λ if using non-integer penalties. Convergence: maintain an invariant like “best λ with c(

λ)

≥ k” to terminate after a fixed number of steps or when low and high cross; after termination, compute the exact-k value using A(

λ *)

−

λ *

k (minimization) or B(

λ *)

λ *

k (maximization).

Code Examples

MST with exactly k special edges (minimize total weight) via WQS + Kruskal

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct DSU {
5     int n; vector<int> p, r;
6     DSU(int n=0): n(n), p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
7     int find(int x){ return p[x]==x? x: p[x]=find(p[x]); }
8     bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
9 };
10 
11 struct Edge { int u,v; long long w; int special; };
12 
13 // Build MST with adjusted weights w' = w + lambda * special.
14 // Returns pair {A(lambda), count_special}, where A(lambda) = sum(w') of MST.
15 pair<long long,int> mst_with_lambda(int n, const vector<Edge>& edges, long long lambda){
16     vector<pair<long long,int>> ord; ord.reserve(edges.size());
17     for(int i=0;i<(int)edges.size();++i){
18         // key = adjusted weight; tie-break by favoring non-special when equal (optional but stable)
19         long long adj = edges[i].w + lambda * (long long)edges[i].special;
20         // store index for access after sort
21         ord.emplace_back(adj, i);
22     }
23     sort(ord.begin(), ord.end(), [&](const auto& a, const auto& b){
24         if(a.first != b.first) return a.first < b.first;
25         // Optional tie-breaker: prefer non-special to keep counts as small as possible at higher lambda
26         return edges[a.second].special < edges[b.second].special;
27     });
28     DSU dsu(n);
29     long long total_adj = 0;
30     int used = 0, cnt_special = 0;
31     for(auto [adj, idx] : ord){
32         const auto &e = edges[idx];
33         if(dsu.unite(e.u, e.v)){
34             total_adj += adj;
35             cnt_special += e.special;
36             used++;
37             if(used == n-1) break;
38         }
39     }
40     if(used != n-1) return { (long long)4e18, 0 }; // graph not connected
41     return { total_adj, cnt_special };
42 }
43 
44 int main(){
45     ios::sync_with_stdio(false); cin.tie(nullptr);
46     int n, m, k; // n nodes, m edges, want exactly k special edges
47     if(!(cin >> n >> m >> k)){
48         // Sample: small graph
49         n = 4; m = 5; k = 2;
50         vector<Edge> edges = {
51             {0,1,5,1},{1,2,2,0},{2,3,3,1},{0,2,4,1},{1,3,6,0}
52         };
53         long long lo = -1e9, hi = 1e9; // broad bounds for lambda
54         long long best_lambda = lo;
55         // Invariant: keep largest lambda with c(lambda) >= k
56         while(lo <= hi){
57             long long mid = lo + (hi - lo)/2;
58             auto [A, c] = mst_with_lambda(n, edges, mid);
59             if(c >= k){ best_lambda = mid; lo = mid + 1; }
60             else hi = mid - 1;
61         }
62         auto [A, c] = mst_with_lambda(n, edges, best_lambda);
63         long long exact = A - best_lambda * (long long)k; // F(k) = A(lambda) - lambda*k
64         cout << exact << "\n";
65         return 0;
66     }
67     vector<Edge> edges(m);
68     for(int i=0;i<m;++i){
69         int u,v,s; long long w; cin >> u >> v >> w >> s; --u; --v; edges[i]={u,v,w,s};
70     }
71     long long lo = -1e12, hi = 1e12; // choose safe bounds per constraints
72     long long best_lambda = lo;
73     while(lo <= hi){
74         long long mid = lo + (hi - lo)/2;
75         auto [A, c] = mst_with_lambda(n, edges, mid);
76         // If MST not possible, move left (but typical CF inputs guarantee connectivity)
77         if(A > (long long)3e18){ hi = mid - 1; continue; }
78         if(c >= k){ best_lambda = mid; lo = mid + 1; }
79         else hi = mid - 1;
80     }
81     auto [A, c] = mst_with_lambda(n, edges, best_lambda);
82     long long exact = A - best_lambda * (long long)k;
83     cout << exact << "\n";
84     return 0;
85 }
86

We want an MST with exactly k special edges and minimal total original weight. Adding λ to the weight of each special edge gives adjusted weights w' = w + λ·special. Kruskal on w' yields an MST whose number of special edges decreases as λ increases. We binary search for the largest λ with c(λ) ≥ k, then recover the exact-k answer by F(k) = A(λ) − λk, where A(λ) is the MST adjusted weight. Sorting ties are handled consistently; 64-bit arithmetic protects against overflow.

Time: O(m log m log R) where R is the λ range and m is the number of edges.Space: O(n + m) for DSU and edge storage.

Maximum sum of exactly k non-overlapping subarrays via WQS DP

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // We maximize the sum of k disjoint subarrays of an array a[0..n-1].
5 // WQS: For a fixed lambda, compute B(lambda) = max(value - lambda * count).
6 // Return pair {B(lambda), count(lambda)} with tie-breaking to prefer larger count when values tie.
7 static inline pair<long long,int> better(pair<long long,int> A, pair<long long,int> B){
8     if(A.first != B.first) return (A.first > B.first) ? A : B;
9     return (A.second > B.second) ? A : B; // prefer larger count on tie
10 }
11 
12 pair<long long,int> solve_lambda(const vector<long long>& a, long long lambda){
13     const long long NEG = (long long)-4e18;
14     pair<long long,int> take = {NEG, 0};     // currently inside a segment, best adjusted value
15     pair<long long,int> rest = {0, 0};       // currently outside any segment, best adjusted value
16     for(long long x : a){
17         // Extend current segment: take + x
18         auto extend = make_pair(take.first + x, take.second);
19         // Start new segment here: rest + (x - lambda), increases count by 1
20         auto start = make_pair(rest.first + x - lambda, rest.second + 1);
21         auto new_take = better(extend, start);
22         // Either continue being outside, or close segment (move from take to rest)
23         auto new_rest = better(rest, take);
24         take = new_take; rest = new_rest;
25     }
26     // Final best can be either resting or still taking (closing implicitly)
27     return better(rest, take);
28 }
29 
30 int main(){
31     ios::sync_with_stdio(false); cin.tie(nullptr);
32     int n; int K;
33     if(!(cin >> n >> K)){
34         vector<long long> a = {1, -2, 3, 4, -1, 2, -5, 3};
35         K = 2; n = (int)a.size();
36         long long lo = - (long long)1e12, hi = (long long)1e12;
37         long long best_lambda = hi; // we will keep the smallest lambda with count >= K? Let's maintain largest with count >= K to be consistent.
38         long long L = lo, R = hi; long long ans_lambda = lo;
39         while(L <= R){
40             long long mid = L + (R - L)/2;
41             auto [val, cnt] = solve_lambda(a, mid);
42             if(cnt >= K){ ans_lambda = mid; L = mid + 1; } // increase lambda to reduce count
43             else R = mid - 1;
44         }
45         auto [B, cnt] = solve_lambda(a, ans_lambda);
46         long long exact = B + ans_lambda * (long long)K; // for maximization with -lambda per segment
47         cout << exact << "\n";
48         return 0;
49     }
50     vector<long long> a(n);
51     for(int i=0;i<n;++i) cin >> a[i];
52     long long lo = -(long long)1e12, hi = (long long)1e12;
53     long long ans_lambda = lo;
54     while(lo <= hi){
55         long long mid = lo + (hi - lo)/2;
56         auto [val, cnt] = solve_lambda(a, mid);
57         if(cnt >= K){ ans_lambda = mid; lo = mid + 1; }
58         else hi = mid - 1;
59     }
60     auto [B, cnt] = solve_lambda(a, ans_lambda);
61     long long exact = B + ans_lambda * (long long)K;
62     cout << exact << "\n";
63     return 0;
64 }
65

We want the maximum total sum of exactly K disjoint subarrays. For a fixed λ, the DP maintains two states: being inside a subarray (take) and being outside (rest). Starting a subarray pays −λ; extending adds the element. We return the adjusted optimum B(λ) = max(sum − λ·segments) along with the number of segments used, with tie-breaking toward larger counts. Binary search on λ finds the largest λ with count ≥ K. The exact-k value is then B(λ*) + λ*·K.

Time: O(n log R), where R is the λ search range and n is the array length.Space: O(1) extra space beyond the input.

Weighted interval scheduling with exactly k intervals via WQS

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Interval: [l, r], weight w. Choose exactly K non-overlapping intervals to maximize total weight.
5 // WQS on lambda with classic DP over sorted-by-end intervals: dp[i] = best on first i intervals.
6 // Each chosen interval pays (w - lambda). We track value and count with tie-break by larger count.
7 
8 struct Interval { long long l, r, w; };
9 
10 static inline pair<long long,int> better(pair<long long,int> A, pair<long long,int> B){
11     if(A.first != B.first) return (A.first > B.first) ? A : B;
12     return (A.second > B.second) ? A : B; // prefer larger count on tie
13 }
14 
15 pair<long long,int> solve_lambda(vector<Interval>& itv, const vector<int>& pred, long long lambda){
16     int n = (int)itv.size();
17     vector<pair<long long,int>> dp(n+1, {0,0}); // dp[0] = {0,0}
18     for(int i=1;i<=n;++i){
19         // Option 1: skip i
20         auto skip = dp[i-1];
21         // Option 2: take i: dp[pred[i]] + (w_i - lambda), count +1
22         auto take = dp[pred[i]]; take.first += itv[i-1].w - lambda; take.second += 1;
23         dp[i] = better(skip, take);
24     }
25     return dp[n];
26 }
27 
28 int main(){
29     ios::sync_with_stdio(false); cin.tie(nullptr);
30     int n; int K;
31     if(!(cin >> n >> K)){
32         vector<Interval> itv = {{1,3,4},{2,5,6},{4,6,5},{6,7,4}}; // sample
33         K = 2; n = (int)itv.size();
34         sort(itv.begin(), itv.end(), [](const Interval& a, const Interval& b){ return a.r < b.r; });
35         vector<long long> ends(n); for(int i=0;i<n;++i) ends[i]=itv[i].r;
36         vector<int> pred(n+1,0);
37         for(int i=1;i<=n;++i){
38             // find last j < i with itv[j-1].r <= itv[i-1].l
39             int j = (int)(upper_bound(ends.begin(), ends.end(), itv[i-1].l) - ends.begin());
40             pred[i] = j; // j in [0..i-1]
41         }
42         long long lo = -(long long)1e12, hi = (long long)1e12, best_lambda = lo;
43         while(lo <= hi){
44             long long mid = lo + (hi - lo)/2;
45             auto [val, cnt] = solve_lambda(itv, pred, mid);
46             if(cnt >= K){ best_lambda = mid; lo = mid + 1; }
47             else hi = mid - 1;
48         }
49         auto [B, cnt] = solve_lambda(itv, pred, best_lambda);
50         long long exact = B + best_lambda * (long long)K; // maximization form
51         cout << exact << "\n";
52         return 0;
53     }
54     vector<Interval> itv(n);
55     for(int i=0;i<n;++i){ cin >> itv[i].l >> itv[i].r >> itv[i].w; }
56     sort(itv.begin(), itv.end(), [](const Interval& a, const Interval& b){ return a.r < b.r; });
57     vector<long long> ends(n); for(int i=0;i<n;++i) ends[i]=itv[i].r;
58     vector<int> pred(n+1,0);
59     for(int i=1;i<=n;++i){
60         int j = (int)(upper_bound(ends.begin(), ends.end(), itv[i-1].l) - ends.begin());
61         pred[i] = j;
62     }
63     long long lo = -(long long)1e12, hi = (long long)1e12, best_lambda = lo;
64     while(lo <= hi){
65         long long mid = lo + (hi - lo)/2;
66         auto [val, cnt] = solve_lambda(itv, pred, mid);
67         if(cnt >= K){ best_lambda = mid; lo = mid + 1; }
68         else hi = mid - 1;
69     }
70     auto [B, cnt] = solve_lambda(itv, pred, best_lambda);
71     long long exact = B + best_lambda * (long long)K;
72     cout << exact << "\n";
73     return 0;
74 }
75

We must select exactly K non-overlapping intervals with maximum total weight. Sort by end time and precompute pred[i], the last interval ending before interval i starts. With WQS, each chosen interval pays weight − λ, giving an O(n) DP after O(n log n) preprocessing. The count returned is monotone in λ if we tie-break toward larger counts. Binary search λ and recover the exact value as B(λ*) + λ*·K.

Time: O(n log n + n log R), dominated by sorting and λ search with O(n) DP per iteration.Space: O(n) for DP and preprocessing arrays.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct DSU {
5	int n; vector<int> p, r;
6	DSU(int n=0): n(n), p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
7	int find(int x){ return p[x]==x? x: p[x]=find(p[x]); }
8	bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
9	};
10
11	struct Edge { int u,v; long long w; int special; };
12
13	// Build MST with adjusted weights w' = w + lambda * special.
14	// Returns pair {A(lambda), count_special}, where A(lambda) = sum(w') of MST.
15	pair<long long,int> mst_with_lambda(int n, const vector<Edge>& edges, long long lambda){
16	vector<pair<long long,int>> ord; ord.reserve(edges.size());
17	for(int i=0;i<(int)edges.size();++i){
18	// key = adjusted weight; tie-break by favoring non-special when equal (optional but stable)
19	long long adj = edges[i].w + lambda * (long long)edges[i].special;
20	// store index for access after sort
21	ord.emplace_back(adj, i);
22	}
23	sort(ord.begin(), ord.end(), [&](const auto& a, const auto& b){
24	if(a.first != b.first) return a.first < b.first;
25	// Optional tie-breaker: prefer non-special to keep counts as small as possible at higher lambda
26	return edges[a.second].special < edges[b.second].special;
27	});
28	DSU dsu(n);
29	long long total_adj = 0;
30	int used = 0, cnt_special = 0;
31	for(auto [adj, idx] : ord){
32	const auto &e = edges[idx];
33	if(dsu.unite(e.u, e.v)){
34	total_adj += adj;
35	cnt_special += e.special;
36	used++;
37	if(used == n-1) break;
38	}
39	}
40	if(used != n-1) return { (long long)4e18, 0 }; // graph not connected
41	return { total_adj, cnt_special };
42	}
43
44	int main(){
45	ios::sync_with_stdio(false); cin.tie(nullptr);
46	int n, m, k; // n nodes, m edges, want exactly k special edges
47	if(!(cin >> n >> m >> k)){
48	// Sample: small graph
49	n = 4; m = 5; k = 2;
50	vector<Edge> edges = {
51	{0,1,5,1},{1,2,2,0},{2,3,3,1},{0,2,4,1},{1,3,6,0}
52	};
53	long long lo = -1e9, hi = 1e9; // broad bounds for lambda
54	long long best_lambda = lo;
55	// Invariant: keep largest lambda with c(lambda) >= k
56	while(lo <= hi){
57	long long mid = lo + (hi - lo)/2;
58	auto [A, c] = mst_with_lambda(n, edges, mid);
59	if(c >= k){ best_lambda = mid; lo = mid + 1; }
60	else hi = mid - 1;
61	}
62	auto [A, c] = mst_with_lambda(n, edges, best_lambda);
63	long long exact = A - best_lambda * (long long)k; // F(k) = A(lambda) - lambda*k
64	cout << exact << "\n";
65	return 0;
66	}
67	vector<Edge> edges(m);
68	for(int i=0;i<m;++i){
69	int u,v,s; long long w; cin >> u >> v >> w >> s; --u; --v; edges[i]={u,v,w,s};
70	}
71	long long lo = -1e12, hi = 1e12; // choose safe bounds per constraints
72	long long best_lambda = lo;
73	while(lo <= hi){
74	long long mid = lo + (hi - lo)/2;
75	auto [A, c] = mst_with_lambda(n, edges, mid);
76	// If MST not possible, move left (but typical CF inputs guarantee connectivity)
77	if(A > (long long)3e18){ hi = mid - 1; continue; }
78	if(c >= k){ best_lambda = mid; lo = mid + 1; }
79	else hi = mid - 1;
80	}
81	auto [A, c] = mst_with_lambda(n, edges, best_lambda);
82	long long exact = A - best_lambda * (long long)k;
83	cout << exact << "\n";
84	return 0;
85	}
86

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// We maximize the sum of k disjoint subarrays of an array a[0..n-1].
5	// WQS: For a fixed lambda, compute B(lambda) = max(value - lambda * count).
6	// Return pair {B(lambda), count(lambda)} with tie-breaking to prefer larger count when values tie.
7	static inline pair<long long,int> better(pair<long long,int> A, pair<long long,int> B){
8	if(A.first != B.first) return (A.first > B.first) ? A : B;
9	return (A.second > B.second) ? A : B; // prefer larger count on tie
10	}
11
12	pair<long long,int> solve_lambda(const vector<long long>& a, long long lambda){
13	const long long NEG = (long long)-4e18;
14	pair<long long,int> take = {NEG, 0}; // currently inside a segment, best adjusted value
15	pair<long long,int> rest = {0, 0}; // currently outside any segment, best adjusted value
16	for(long long x : a){
17	// Extend current segment: take + x
18	auto extend = make_pair(take.first + x, take.second);
19	// Start new segment here: rest + (x - lambda), increases count by 1
20	auto start = make_pair(rest.first + x - lambda, rest.second + 1);
21	auto new_take = better(extend, start);
22	// Either continue being outside, or close segment (move from take to rest)
23	auto new_rest = better(rest, take);
24	take = new_take; rest = new_rest;
25	}
26	// Final best can be either resting or still taking (closing implicitly)
27	return better(rest, take);
28	}
29
30	int main(){
31	ios::sync_with_stdio(false); cin.tie(nullptr);
32	int n; int K;
33	if(!(cin >> n >> K)){
34	vector<long long> a = {1, -2, 3, 4, -1, 2, -5, 3};
35	K = 2; n = (int)a.size();
36	long long lo = - (long long)1e12, hi = (long long)1e12;
37	long long best_lambda = hi; // we will keep the smallest lambda with count >= K? Let's maintain largest with count >= K to be consistent.
38	long long L = lo, R = hi; long long ans_lambda = lo;
39	while(L <= R){
40	long long mid = L + (R - L)/2;
41	auto [val, cnt] = solve_lambda(a, mid);
42	if(cnt >= K){ ans_lambda = mid; L = mid + 1; } // increase lambda to reduce count
43	else R = mid - 1;
44	}
45	auto [B, cnt] = solve_lambda(a, ans_lambda);
46	long long exact = B + ans_lambda * (long long)K; // for maximization with -lambda per segment
47	cout << exact << "\n";
48	return 0;
49	}
50	vector<long long> a(n);
51	for(int i=0;i<n;++i) cin >> a[i];
52	long long lo = -(long long)1e12, hi = (long long)1e12;
53	long long ans_lambda = lo;
54	while(lo <= hi){
55	long long mid = lo + (hi - lo)/2;
56	auto [val, cnt] = solve_lambda(a, mid);
57	if(cnt >= K){ ans_lambda = mid; lo = mid + 1; }
58	else hi = mid - 1;
59	}
60	auto [B, cnt] = solve_lambda(a, ans_lambda);
61	long long exact = B + ans_lambda * (long long)K;
62	cout << exact << "\n";
63	return 0;
64	}
65

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Interval: [l, r], weight w. Choose exactly K non-overlapping intervals to maximize total weight.
5	// WQS on lambda with classic DP over sorted-by-end intervals: dp[i] = best on first i intervals.
6	// Each chosen interval pays (w - lambda). We track value and count with tie-break by larger count.
7
8	struct Interval { long long l, r, w; };
9
10	static inline pair<long long,int> better(pair<long long,int> A, pair<long long,int> B){
11	if(A.first != B.first) return (A.first > B.first) ? A : B;
12	return (A.second > B.second) ? A : B; // prefer larger count on tie
13	}
14
15	pair<long long,int> solve_lambda(vector<Interval>& itv, const vector<int>& pred, long long lambda){
16	int n = (int)itv.size();
17	vector<pair<long long,int>> dp(n+1, {0,0}); // dp[0] = {0,0}
18	for(int i=1;i<=n;++i){
19	// Option 1: skip i
20	auto skip = dp[i-1];
21	// Option 2: take i: dp[pred[i]] + (w_i - lambda), count +1
22	auto take = dp[pred[i]]; take.first += itv[i-1].w - lambda; take.second += 1;
23	dp[i] = better(skip, take);
24	}
25	return dp[n];
26	}
27
28	int main(){
29	ios::sync_with_stdio(false); cin.tie(nullptr);
30	int n; int K;
31	if(!(cin >> n >> K)){
32	vector<Interval> itv = {{1,3,4},{2,5,6},{4,6,5},{6,7,4}}; // sample
33	K = 2; n = (int)itv.size();
34	sort(itv.begin(), itv.end(), [](const Interval& a, const Interval& b){ return a.r < b.r; });
35	vector<long long> ends(n); for(int i=0;i<n;++i) ends[i]=itv[i].r;
36	vector<int> pred(n+1,0);
37	for(int i=1;i<=n;++i){
38	// find last j < i with itv[j-1].r <= itv[i-1].l
39	int j = (int)(upper_bound(ends.begin(), ends.end(), itv[i-1].l) - ends.begin());
40	pred[i] = j; // j in [0..i-1]
41	}
42	long long lo = -(long long)1e12, hi = (long long)1e12, best_lambda = lo;
43	while(lo <= hi){
44	long long mid = lo + (hi - lo)/2;
45	auto [val, cnt] = solve_lambda(itv, pred, mid);
46	if(cnt >= K){ best_lambda = mid; lo = mid + 1; }
47	else hi = mid - 1;
48	}
49	auto [B, cnt] = solve_lambda(itv, pred, best_lambda);
50	long long exact = B + best_lambda * (long long)K; // maximization form
51	cout << exact << "\n";
52	return 0;
53	}
54	vector<Interval> itv(n);
55	for(int i=0;i<n;++i){ cin >> itv[i].l >> itv[i].r >> itv[i].w; }
56	sort(itv.begin(), itv.end(), [](const Interval& a, const Interval& b){ return a.r < b.r; });
57	vector<long long> ends(n); for(int i=0;i<n;++i) ends[i]=itv[i].r;
58	vector<int> pred(n+1,0);
59	for(int i=1;i<=n;++i){
60	int j = (int)(upper_bound(ends.begin(), ends.end(), itv[i-1].l) - ends.begin());
61	pred[i] = j;
62	}
63	long long lo = -(long long)1e12, hi = (long long)1e12, best_lambda = lo;
64	while(lo <= hi){
65	long long mid = lo + (hi - lo)/2;
66	auto [val, cnt] = solve_lambda(itv, pred, mid);
67	if(cnt >= K){ best_lambda = mid; lo = mid + 1; }
68	else hi = mid - 1;
69	}
70	auto [B, cnt] = solve_lambda(itv, pred, best_lambda);
71	long long exact = B + best_lambda * (long long)K;
72	cout << exact << "\n";
73	return 0;
74	}
75