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

Sum of Adjacent Minimums

Back to problem

Editorial

Consider

M=max⁡1≤l<r≤Nr−lCl+Cl+1+⋯+Cr.M=\max_{1\leq l<r\leq N}\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}.M=1≤l<r≤Nmax​Cl​+Cl+1​+⋯+Cr​.

The answer is XMXMXM. Thus, using prefix sums and checking every interval [l,r][l,r][l,r] solves the problem in O(N2)O(N^2)O(N2) time.

Intuition

Suppose from the beginning that some optimal solution has the following form.

0,⋯ ,0,H,H,⋯ ,H,0,⋯ ,00,\cdots,0,H,H,\cdots,H,0,\cdots,00,⋯,0,H,H,⋯,H,0,⋯,0

If the positive part is the interval , then the condition determines

Proof

Fix any feasible R1,R2,⋯ ,RNR_1,R_2,\cdots,R_NR1​,R2​,⋯,R. For a nonnegative real number , keep exactly the indices satisfying . The remaining indices form a disjoint union of contiguous intervals.

Solution written by GPT5.6

r−l
​
[l,r][l,r]
[l,r]
C1R1+C2R2+⋯+CNRN=XC_1R_1+C_2R_2+\cdots+C_NR_N=XC1​R1​+C2​R2​+⋯+CN​RN​=X
H=XCl+Cl+1+⋯+Cr.H=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}.H=Cl​+Cl+1​+⋯+Cr​X​.

The objective value is then (r−l)H=Xr−lCl+Cl+1+⋯+Cr(r-l)H=X\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}(r−l)H=XCl​+Cl+1​+⋯+Cr​r−l​.

Therefore, among solutions of this form, the best interval is one maximizing r−lCl+Cl+1+⋯+Cr\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}Cl​+Cl+1​+⋯+Cr​r−l​, and it achieves XMXMXM. It remains only to prove that no more complicated choice of R1,R2,⋯ ,RNR_1,R_2,\cdots,R_NR1​,R2​,⋯,RN​ can exceed XMXMXM.

N
​
ttt
iii
Ri≥tR_i\geq tRi​≥t

For one such interval [l,r][l,r][l,r], there are r−lr-lr−l adjacent pairs whose two indices both remain. By the definition of MMM, (r−l)≤M(Cl+Cl+1+⋯+Cr)(r-l)\leq M(C_l+C_{l+1}+\cdots+C_r)(r−l)≤M(Cl​+Cl+1​+⋯+.

Summing over all remaining intervals, at height ttt the number of adjacent pairs whose two indices remain is at most M∑1≤i≤NRi≥tCiM\displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_iM1≤i≤NRi​≥t​∑​Ci​.

Let K(t)K(t)K(t) be the number of adjacent pairs whose two indices remain at height ttt. Each pair (i,i+1)(i,i+1)(i,i+1) is counted exactly while 0≤t≤min⁡(Ri,Ri+1)0\leq t\leq\min(R_i,R_{i+1})0≤t≤min(Ri​,Ri+1​), so the objective value is ∫0∞K(t) dt\int_0^\infty K(t)\,dt∫0∞​K(t)dt. Therefore, integrating the inequality above over all t≥0t\geq 0t≥0 gives

∫0∞K(t) dt≤M∫0∞∑1≤i≤NRi≥tCi dt=M∑i=1NCiRi=MX.\begin{aligned} \int_0^\infty K(t)\,dt &\leq M\int_0^\infty \displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_i\,dt \\ &=M\sum_{i=1}^{N}C_iR_i \\ &=MX. \end{aligned}∫0∞​K(t)dt​≤M∫0∞​1≤i≤NR

Now choose an interval [l,r][l,r][l,r] attaining MMM. For every l≤i≤rl\leq i\leq rl≤i≤r, set

Ri=XCl+Cl+1+⋯+Cr,R_i=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r},Ri​=Cl​+Cl+1​+⋯+Cr​X​,

and set all other RiR_iRi​ to 000. This satisfies the constraint, and the objective value is XMXMXM.

Therefore, XMXMXM is exactly the maximum value.

Cr​
)
i
​
≥
t
​
∑
​
Ci​
d
t
=Mi=1∑N​Ci​Ri​
=MX.
​