g5-09159. 至少与恰好 未做

工坊里 $n$ 道工序必须按 $1$ 到 $n$ 的固定顺序加工。工人每天从上一天的断点继续,当天累计工时不能超过上限 $cap$;若下一道工序连新开一天单独加工都放不下,即它的工时大于 $cap$,流水停摆,其后所有工序都无法完成。记 $f(cap)$ 为停摆前能完成的工序道数。请分别求出使 $f(cap)\ge k$ 的最小 $cap$ 与使 $f(cap)=k$ 的最小 $cap$,并判断两者是否相同:相同输出 SAME,否则输出 DIFF。若恰好完成 $k$ 道的上限不存在,第二行输出 $-1$。

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $w_i$,为各工序的工时。

共三行:第一行 $c_1$,即使 $f(cap)\ge k$ 的最小 $cap$;第二行 $c_2$,即使 $f(cap)=k$ 的最小 $cap$,不存在输出 $-1$;第三行输出 SAME 或 DIFF。

$c_1$:$cap=5$ 时工序 $1$ 用 $3$,工序 $2$ 用 $5$,工序 $3$ 需 $9>5$,停摆,$f(5)=2$;更小的 $cap$ 连工序 $2$ 都放不下,故 $c_1=5$。$c_2$:$cap$ 取 $5$ 到 $8$ 时都有 $f(cap)=2$(工序 $3$ 的 $9$ 单独一天也放不下),最小为 $5$,故 $c_2=5$。两者相同,第三行输出 SAME。

$1\le k\le n\le 2\times 10^5$;$1\le w_i\le 10^9$。