Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sgt. Laugh

By reborn · Limits 2.5s, 256 MB

That's it. Sgt. Laugh has had enough. He is determined to end the evil military reign of General Cry. But Laugh isn't stupid. He knows, he needs a team to break through the walls of Cry.

Platoon "BattleCry'' has nn soldiers. Laugh will choose kk of these soldiers. The platoon is lined up. Height of the soldier ii is represented by hih_i. The sergeant wiil choose the soldiers in a way so that their heights form a strictly increasing sequence, i.e. if he chooses soldiers with indices i1, i2,.. ik1, iki_1, ~i_2, .. ~i_{k-1}, ~i_k where i1<i2<i3..<iki_1 < i_2 < i_3 .. < i_k , condition hi1<hi2<hi3..<hikh_{i_1} < h_{i_2} < h_{i_3} .. < h_{i_k} must hold. Also since the sergeant is a little bit picky, the height difference between the tallest and shortest soldier must be minimum possible.

Help Laugh choose the squad.


First line of input contains two integers n, kn, ~k .
The following line contains nn integers representing the heights of the soldiers hih_i.


  • 1n2×1051 \leq n \leq 2 \times 10^5 .
  • 1kmin(n, 30)1 \leq k \leq \min(n, ~30) .
  • 1hi1091 \leq h_i \leq 10^9 .


If no such squad could be formed, print 1-1 on a line.

Otherwise, output the minimum possible difference between the tallest and shortest soldier in the chosen squad.


5 3
12 14 11 12 15
5 3
5 4 1 4 4



39% Solution Ratio

tmwilliamlin168Earliest, Jan '20

tmwilliamlin168Fastest, 0.7s

Mr_BangladeshLightest, 12 MB

Deshi_TouristShortest, 950B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.