Sorting and chains Sort each module's candidates by nondecreasing performance. Write the sorted performance and consumption as . Always move each pair together.
Create vertices for module , with and . A vertex on the source side means that the chosen candidate index exceeds . Add an infinite-capacity reverse edge for every . In a finite cut, source-side vertices form a prefix, and exactly one forward chain edge is cut. A module with has just one forward edge from to .
Products For each mine, orient its two modules as in input order, and denote their selected performances by .
The last term equals . For every and , add an edge from to with capacity . Zero increments allow these edges to be omitted. Process repeated mines separately.
Unary costs and recovery
For every , give the forward edge capacity , which is positive. Candidate selections correspond bijectively to finite cuts. The cut capacity is the negative net profit plus . Hence a minimum cut gives the optimum.
Bounds and complexity The answer lies between and . We have , , , and . The total penalty capacity for one mine is . The sum of all finite capacities is less than , so suffices as infinity. All arithmetic fits in signed 64-bit integers.
There are at most vertices and added edges, excluding residual reverse edges. Dinic has general time complexity and space complexity .
Subtasks For subtask 1, enumerate all candidate combinations in time; there are at most combinations. In subtask 2, each module has at most one binary decision, giving at most one cut vertex per module. Subtask 3 uses the complete chains. The additional correct solution uses the independent threshold expansion to cross-check the construction.
Solution written by GPT6