Overview

This is a “minimize (Aoki) → maximize (Takahashi)” problem where Aoki cancels exactly \(K\) jobs to minimize Takahashi’s maximum profit. Since \(N \le 8\) is small, we can enumerate all possible cancellation sets and execution sets using bitmask enumeration to find the answer.

Analysis

Key Observations

• The set of jobs Takahashi chooses must be “mutually non-overlapping (compatible).” In other words, the chosen set must contain no conflicts (overlaps) whatsoever.
• Since Aoki anticipates that “Takahashi will act optimally after cancellations,” the value we ultimately want is: [ \min{\text{cancellation set }C,\ |C|=K}\ \max{\text{execution set }S\subseteq \overline{C},\ S\text{ is compatible}}\ \sum_{i\in S}V_i ] which is a min-max problem.

Naive Approach

• Aoki has \(\binom{N}{K}\) possible cancellation sets, and Takahashi has \(2^{N-K}\) possible choices.
• However, since \(N \le 8\), even in the worst case \(2^N \times 2^N = 4^N = 65536\) is more than fast enough (with minor optimizations, it’s very comfortable).

How to Solve It

• Represent job sets as bitmasks (0/1 strings of length \(N\)).
• First, checking “is a given set compatible?” by comparing intervals pairwise each time is cumbersome, so we precompute conflict relationships using bits.
• Furthermore, for all subsets, precompute:
  • Total reward val_sum[mask]
  • Whether the set is compatible valid[mask]

This allows us to quickly search for “maximum reward among remaining jobs” for each cancellation set.

Algorithm

1. Store conflicts between jobs as bits

The condition for jobs \(i\) and \(j\) to overlap is the negation of the compatibility condition: [ \neg(R_i \le L_j \ \text{or}\ R_j \le L_i) ] If they overlap, set bit \(j\) in conflict[i].

2. Precompute “total value” and “compatibility” for all subsets in a DP-like manner

Extract the lowest set bit (lsb) of mask, and let that element be \(i\).

• rest = mask ^ lsb (the set excluding \(i\))
• Total reward: [ \text{val_sum}[mask] = \text{val_sum}[rest] + V_i ]
• Compatibility:
  • rest itself is compatible, and
  • \(i\) does not conflict with any element in rest (rest & conflict[i] == 0)

If both hold, set valid[mask] = True.

This allows checking “is a set compatible?” in \(O(1)\).

3. Enumerate all cancellation sets for Aoki and find Takahashi’s optimal value for each

• Enumerate cancel from \(0\) to \(2^N-1\), only considering those where cancel.bit_count() == K.
• remaining = all_mask ^ cancel is the set of remaining jobs.
• Takahashi takes the maximum val_sum[subset] among subsets subset of remaining satisfying:
  • subset is contained in remaining: (subset & ~remaining) == 0
  • valid[subset] == True
• Let this maximum be best. Since Aoki wants to minimize it, update ans = min(ans, best).

Complexity

• Time complexity:
  • Conflict precomputation \(O(N^2)\)
  • Subset precomputation \(O(2^N)\)
  • Cancellation enumeration \(O(2^N)\), with subset search \(O(2^N)\) for each cancellation

Total: [ O(N^2 + 4^N) ] (Fast enough for \(N \le 8\)) - Space complexity: [ O(2^N) ] (for val_sum, valid, etc.)

Implementation Notes

• Intervals are half-open \([L_i, R_i)\), so for example when \(R_i = L_j\), they do not overlap and are compatible. Using not (R[i] <= L[j] or R[j] <= L[i]) for conflict detection is safe.

• Checking “is a set contained in the remaining set” can be concisely written with bit operations as: subset & ~remaining == 0

• Building valid[mask] by “adding one element at a time” avoids having to perform \(O(N^2)\) compatibility checks each time.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = [0] * N
    R = [0] * N
    V = [0] * N
    for i in range(N):
        L[i], R[i], V[i] = map(int, input().split())

    conflict = [0] * N
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if not (R[i] <= L[j] or R[j] <= L[i]):
                conflict[i] |= 1 << j

    M = 1 << N
    val_sum = [0] * M
    valid = [False] * M
    valid[0] = True

    for mask in range(1, M):
        lsb = mask & -mask
        i = (lsb.bit_length() - 1)
        rest = mask ^ lsb
        val_sum[mask] = val_sum[rest] + V[i]
        valid[mask] = valid[rest] and ((rest & conflict[i]) == 0)

    all_mask = M - 1
    ans = 10**18
    for cancel in range(M):
        if cancel.bit_count() != K:
            continue
        remaining = all_mask ^ cancel
        best = 0
        for subset in range(M):
            if (subset & ~remaining) == 0 and valid[subset]:
                s = val_sum[subset]
                if s > best:
                    best = s
        if best < ans:
            ans = best

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.