Problem:


Score : 600 points

Problem Statement

You are given an integer sequence A of length N and an integer K.
You will perform the following operation on this sequence Q times:

Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible.
Find the smallest possible value of X-Y when the Q operations are performed optimally.

Constraints

1 \leq N \leq 2000

1 \leq K \leq N

1 \leq Q \leq N-K+1

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 ... A_N

Output

Print the smallest possible value of X-Y.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1.
Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2).
In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2.
In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Sample Input 2

10 1 6
1 1 2 3 5 8 13 21 34 55

Sample Output 2

7

Sample Input 3

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

Sample Output 3

451211184



Sample input:
5 3 2
4 3 1 5 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def n_removable(N, ix, K):
    # ix is sorted
    cnt = max(0, ix[0] - K + 1)
    for j in range(len(ix) - 1):
        cnt += max(0, ix[j+1] - ix[j] - K)
    cnt += max(0, N - ix[-1] - K)
    return cnt


def manage_luck_flag(luck_flag, j, K):
    luck_flag[j] = 1
    N = len(luck_flag)
    if j < K:
        luck_flag[:j+1] = 1
    if j >= N - K:
        luck_flag[-j-1:] = 1
    if K <= j < N - K:
        for k in range(1, K+1):
            if luck_flag[j - k] == 1:
                for p in range(k+1):
                    luck_flag[j - p] = 1
                break
        for k in range(1, K+1):
            if luck_flag[j + k] == 1:
                for p in range(k+1):
                    luck_flag[j + p] = 1
                break  
    
    return luck_flag


def main(N, K, Q, A):
    A = np.array(A)
    Asort = np.sort(A)
    ix = np.argsort(A)
    luck_ix = []

    diff = Asort[Q-1] - Asort[0]

    luck_flag = np.zeros(N)

    for i in range(N-Q-1):
        bisect.insort(luck_ix, ix[i])
        luck_flag = manage_luck_flag(luck_flag, ix[i], K)

        cnt = n_removable(N, luck_ix, K)
        if Q > cnt:
            return diff

        Asortd = np.sort(A[(1 - luck_flag).astype(bool)])
        # print(luck_flag, Asortd)
        if len(Asortd) < Q:
            return diff

        diff = min(diff, Asortd[Q-1] - Asortd[0])

    return diff

if __name__ == '__main__':
    N, K, Q = lii()
    A = lii()
    print(main(N, K, Q, A))
    exit()

    # for _ in range(100):
    #     N = 2000
    #     K = np.random.randint(N) + 1
    #     Q = np.random.randint(N - K + 1) + 1
    #     A = np.random.randint(20, size=N)
    #     # print(N, K, Q, A)
    #     print(main(N, K, Q, A))

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
print(sorted(a)[q-1] - sorted(a)[0])

Submission status: Wrong Answer

Solution code:
import functools
a = [int(x) for x in input().split()]
N = a[0]
K = a[1]
Q = a[2]
b = sorted([int(x) for x in input().split()])
c = [0] * (N-K-Q+2)
for k in range(len(c)):
  c[k] = b[k + Q - 1] - b[k]
d = functools.reduce(lambda x,y:min(x,y),c)
print(d)

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = []
coli = []
if k + q > n:
	print(lis[q-1]-lis[0])
	exit()
for h in range(q):
	for i in range(k):
		li.append(lis[i+h])
		coli.append(i)
		
		
print(min(li))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            if i == n:
                ma = 99999999999
            else:
                ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t >= ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n+1)
        # print(i,l,mi)
        if l > n or l <= i+1:
            continue
        t = sa[l-1] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = sorted(list(map(int,input().split())))

print(A[Q-1]-A[0])

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t >= ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n)
        # print(i,l,mi)
        if l >= n or l <= i:
            continue
        t = sa[l-1] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
# E
from heapq import heappush, heappop
import numpy as np

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

A_args = np.argsort(A)

nodeid = np.ones(N).astype("int32")
canput = np.ones(N)
nodeid_dict = dict()
nodeid_dict[1] = [0, N]
# initial output
res = A[A_args[Q-1]] - A[A_args[0]]

ind_del = 0

for i in range(N):
    
    nid = A_args[i]
    
    # update nodeid
    ndid = nodeid[nid]
    nodeid[nid] = 0
    left, right = nodeid_dict[ndid]
    nodeid[(nid+1):right] = i+2
    nodeid_dict[nid] = [left, nid]
    nodeid_dict[i+2] = [nid+1, right]

    # update canput
    canput[nid] = 0
    
    canput[left:nid] = 0
    h = []
    for j in range(left, nid):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    canput[(nid+1):right] = 0
    h = []
    for j in range(nid+1, right):
        heappush(h, (-A[j], j))
    while len(h) >= K:
        _, j = heappop(h)
        canput[j] = 1
    
    # break
    if canput.sum() <= Q:
        break
        
    # calculate
    q = 0
    qmin = 10**9
    qmax = 1
    for i in range(N):
        if canput[A_args[i]] == 1:
            q += 1
            qmin = min(A[A_args[i]], qmin)
            qmax = max(A[A_args[i]], qmax)
            if q == Q:
                r = qmax - qmin
    res = min(res, r)
print(res)

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9
if 2 * k >= n:
	print(lis[q-1]-lis[0])
	exit()
for i in range(n-k):
	try:
		li = min(li,lis[i+q-1]-lis[i])
	except:
		pass
print(li)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t > ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n)
        # print(i,l,mi)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9
if k + q > n:
	print(lis[q-1]-lis[0])
	exit()
for i in range(n-k):
	try:
		li = min(li,lis[i+q-1]-lis[i])
	except:
		pass
print(li)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = [(int(x), i) for i, x in enumerate(input().split())]
a.sort()
m = a[q - 1][0] - a[0][0]
v = []
for i in range(1, n - q + 1):
    mi = a[q - 1 + i][0] - a[i][0]
    v.append((mi, i))
v.sort()
for mi, i in v:
    if mi >= m: break
    ok = True
    for ai in range(i, i + q):
        for bi in range(i):
            if abs(a[bi][1] - a[ai][1]) < k:
                ok = False
                break
        if not ok: break
    if ok:
        m = mi
        break
print(m)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t > ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, i, n)
        # print(i,l,mi)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9

for i in range(n-k-q+2):
	li = min(li,lis[i+q-1]-lis[i])
print(li)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t > ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, i+1, n)
        # print(i,l,mi)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9
if k + q > n:
	print(lis[q-1]-lis[0])
	exit()
for i in range(n-k-q+2):
	li = min(li,lis[i+q-1]-lis[i])
print(li)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int,input().split())
A_input = list(map(int, input().split()))

def make_min_array(A):
    A_min = []
    for i in range(len(A) - k + 1):
        tmp = A[i]
        for j in range(i, len(A)):
            tmp = min(tmp, A[j])
            A_min.append(tmp)
    return A_min

A_out = []
for i in range(q):
    tmp = min(make_min_array(A_input))
    A_out.append(tmp)
    A_input.remove(tmp)



print(max(A_out)-min(A_out))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t > ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, i+q-1, n)
        # print(i,l,mi)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
ans = a[q - 1] - a[0]

while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != a[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
    newd.append(li)

    d = list()
    mi = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li = sorted(li)
            mi.extend(li[0:len(li) - k + 1])
 
    mi.sort()

    if len(mi) >= q:
        a.pop(0)
        ans = min(mi[q - 1] - mi[0], ans)
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!python
# -*- coding: utf-8 -*-


def main():
    N, K, Q = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    print(A[Q - 1] - A[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k,q=map(int, input().split())
a=list(map(int, input().split()))
a2=sorted(a)
if q==1:print(a2[0])
else: print(a2[q-1]-a2[0])

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
sa = sorted(a)
ans = sa[q - 1] - sa[0]

while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != sa[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
    newd.append(li)

    w = 0
    d = list()
    mi = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            w += len(li) - k + 1
            d.append(li)
            li.sort()
            mi.extend(li[0:len(li) - k + 1])

    mi.sort()

    if w >= q:
        sa.pop(0)
        ans = min(mi[q - 1] - mi[0], ans)
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n,k,q=map(int, input().split())
a=list(map(int, input().split()))
a2=sorted(a)
print(a2[q-1]-a2[0])

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9
if 2 * k >= n:
	print(lis[q-1]-lis[0])
	exit()
for i in range(n-k-q+2):
	li = min(li,lis[i+q-1]-lis[i])
print(li)

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
li = 10 ** 9

for i in range(n-k-q+2):
	li = min(li,lis[i+q-1]-lis[i])
print(li)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
sa = sorted(a)
ans = sa[q - 1] - sa[0]

while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != sa[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
    newd.append(li)

    w = 0
    d = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            w += len(li) - k + 1
            d.append(li)

    if w >= q:
        sa = sa[1:]
        ans = min(sa[q - 1] - sa[0], ans)
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            g = 0
            for t in a:
                if t < mi or t > ma:
                    if c > k:
                        g += c - k
                    c = 0
                    continue
                c += 1
            if c > k:
                g += c - k
            return g < q

        l = bs(f, i, n)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a.sort()
ans = a[q - 1] - a[0]

while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != a[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
    newd.append(li)

    w = 0
    d = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            w += len(li) - k + 1
            d.append(li)

    if w >= q:
        a = a[1:]
        ans = min(a[q - 1] - a[0], ans)
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            g = 0
            for t in a:
                if t < mi or t > ma:
                    if c > k:
                        g += c - k
                    c = 0
                    continue
                c += 1
            if c > k:
                g += c - k
            return g < q

        l = bs(f, i+q-1, n)
        if l >= n or l <= i:
            continue
        t = sa[l] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
n, k, q = map(int,input().split())
A = list(map(int, input().split()))


A.sort()

print(A[q - 1] - A[0])

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
print(lis[q-1]-lis[0])

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        for j in range(q-1+i, n):
            t = sa[j] - sa[i]
            # print(i, t)
            if t >= r:
                break
            c = sorted([_[1] for _ in bb if _[0] <= sa[i] or _[0] > sa[j]]) + [n]
            e = -1
            g = 0
            for d in c:
                if d - e < 2:
                    e = d
                    continue
                f = d - e - 1
                if f > k:
                    g += f - k
                e = d
            # print('g',g,q)
            if g >= q:
                r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        for j in range(q-1+i, n):
            t = sa[j] - sa[i]
            # print(i, t)
            if t >= r:
                break
            c = sorted([_[1] for _ in bb if _[0] <= sa[i] and _[0] > sa[j]]) + [n]
            e = -1
            g = 0
            for d in c:
                if d - e < 2:
                    e = d
                    continue
                f = d - e - 1
                if f > k:
                    g += f - k
                e = d
            # print('g',g,q)
            if g >= q:
                r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        for j in range(q-1+i, n):
            t = sa[j] - sa[i]
            # print(i, t)
            if t >= r:
                break
            c = sorted([_[1] for _ in bb if _[0] <= sa[i]]) + [n]
            e = -1
            g = 0
            for d in c:
                if d - e < 2:
                    e = d
                    continue
                f = d - e - 1
                if f > k:
                    g += f - k
                e = d
            # print('g',g,q)
            if g >= q:
                r = t


    return r




print(main())