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

Dungeon Raid

Back to problem

Editorial

At level XXX, only dungeons satisfying Ai<XA_i < XAi​<X need to be considered. Challenging any other dungeon does not increase the level, so doing so cannot be better than postponing it.

Among the currently available dungeons, choose one with the smallest BiB_iBi​. If its second difficulty value is BBB, the new level is

X+min⁡(X,B).X+\min(X,B).X+min(X,B).

For two currently available dungeons with second difficulty values b≤cb \leq cb≤c, challenging them in the order b,cb,cb,c leaves the level at least as large as challenging them in the order c,bc,bc,b. Repeating this exchange argument shows that choosing the smallest available BiB_iB first does not lose an optimal solution.

Sort the dungeons by AiA_iAi​. Insert every BiB_iBi​ whose dungeon satisfies Ai<XA_i < XA into a min-heap, remove the smallest value, and update the level. If the heap is empty, none of the remaining dungeons can increase the level, so the process ends.

The time complexity is O(Nlog⁡N)O(N\log N)O(NlogN) and the space complexity is O(N)O(N)O(N). The final level is at most L+∑Bi≤5.00001×1017L+\sum B_i \leq 5.00001\times 10^{17}L+∑B, which fits in a signed 64-bit integer.

Solution written by GPT5

i
​
i
​
<
X
i​
≤
5.00001×
1017