DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Dadas at Work

Back to problem

Editorial

Sorting and chains Sort each module's candidates by nondecreasing performance. Write the sorted performance and consumption as bi,j,ci,jb_{i,j},c_{i,j}bi,j​,ci,j​. Always move each pair together.

di,k=bi,k+1−bi,k≥0(1≤k<Ai).d_{i,k}=b_{i,k+1}-b_{i,k}\geq 0\qquad(1\leq k<A_i).di,k​=bi,k+1​

Create Ai−1A_i-1Ai​−1 vertices vi,1,…,vi,Ai−1v_{i,1},\ldots,v_{i,A_i-1}vi,1​, 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 u,vu,vu,v in input order, and denote their selected performances by Bu,BvB_u,B_vBu​,Bv​.

−BuBv=−bv,1Bu−bu,AuBv+bu,Aubv,1+(bu,Au−Bu)(Bv−bv,1).-B_uB_v=-b_{v,1}B_u-b_{u,A_u}B_v+b_{u,A_u}b_{v,1}+(b_{u,A_u}-B_u)(B_v-b_{v,1}).−Bu​B

The last term equals ∑k,ldu,kdv,l[vu,k∈T][vv,l∈S]\sum_{k,l}d_{u,k}d_{v,l}[v_{u,k}\in T][v_{v,l}\in S]∑k,l​du,k​d. 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

αi=∑k:Uk=ibVk,1+∑k:Vk=ibUk,AUk,qi(j)=ci,j−αibi,j.\alpha_i=\sum_{k:U_k=i}b_{V_k,1}+\sum_{k:V_k=i}b_{U_k,A_{U_k}},\qquad q_i(j)=c_{i,j}-\alpha_i b_{i,j}.αi​= K=1+max⁡(0,max⁡i,j(−qi(j))).K=1+\max\left(0,\max_{i,j}(-q_i(j))\right).K=1+max(0,i,jmax​(−q

For every 1≤j≤Ai1\leq j\leq A_i1≤j≤Ai​, give the forward edge vi,j−1→vi,jv_{i,j-1}\to v_{i,j}vi 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.

answer=MK−mincut⁡−∑k=1NbUk,AUkbVk,1.\text{answer}=MK-\operatorname{mincut}-\sum_{k=1}^{N}b_{U_k,A_{U_k}}b_{V_k,1}.answer=MK−mincut−k=1∑

Bounds and complexity The answer lies between −49 998-49\,998−49998 and 999 999 998999\,999\,998999999998. We have αi≤106\alpha_i\leq10^6αi​≤10, , , 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 V=452V=452V=452 vertices and E=82 000E=82\,000E=82000 added edges, excluding residual reverse edges. Dinic has general time complexity O(V2E)O(V^2E)O(V2E) and space complexity .

Subtasks For subtask 1, enumerate all candidate combinations in O((N+M)∏iAi)O((N+M)\prod_i A_i)O((N+M)∏i​Ai​) time; there are at most 10610^6 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

−
bi,k​≥
0(1≤
k<
Ai​).
…
,
vi,Ai​−1​
iii
vi,0=Sv_{i,0}=Svi,0​=S
vi,Ai=Tv_{i,A_i}=Tvi,Ai​​=T
vi,kv_{i,k}vi,k​
kkk
vi,k→vi,k−1v_{i,k}\to v_{i,k-1}vi,k​→vi,k−1​
1≤k≤Ai1\leq k\leq A_i1≤k≤Ai​
Ai=1A_i=1Ai​=1
SSS
TTT
v
​
=
−bv,1​Bu​−
bu,Au​​Bv​+
bu,Au​​bv,1​+
(bu,Au​​−
Bu​)(Bv​−
bv,1​).
v,l​
[
vu,k​
∈
T][vv,l​∈
S]
1≤k<Au1\leq k<A_u1≤k<Au​
1≤l<Av1\leq l<A_v1≤l<Av​
vv,lv_{v,l}vv,l​
vu,kv_{u,k}vu,k​
du,kdv,ld_{u,k}d_{v,l}du,k​dv,l​
k:Uk​=i∑​
bVk​,1​
+
k:Vk​=i∑​bUk​,AUk​​​,qi​(j)=
ci,j​−
αi​bi,j​.
i​
(
j
))
)
.
,
j
−
1
​
→
vi,j​
K+qi(j)K+q_i(j)K+qi​(j)
MK−∑kbUk,AUkbVk,1MK-\sum_k b_{U_k,A_{U_k}}b_{V_k,1}MK−∑k​bUk​,AUk​​​bVk​,1​
N
​
bUk​,AUk​​​
bVk​,1​
.
6
1−109≤qi(j)≤10001-10^9\leq q_i(j)\leq10001−109≤qi​(j)≤1000
K≤109K\leq10^9K≤109
MK≤5⋅1010MK\leq5\cdot10^{10}MK≤5⋅1010
(bu,Au−bu,1)(bv,Av−bv,1)≤9992(b_{u,A_u}-b_{u,1})(b_{v,A_v}-b_{v,1})\leq999^2(bu,Au​​−bu,1​)(bv,Av​​−bv,1​)≤9992
5.01⋅10115.01\cdot10^{11}5.01⋅1011
101510^{15}1015
O(V+E)O(V+E)O(V+E)
106
−wxy=wx(1−y)−wx-wxy=wx(1-y)-wx−wxy=wx(1−y)−wx