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: Accepted

Solution code:
import heapq

def main():
    _, k, q = map(int, input().split())
    a = tuple(map(int, input().split()))

    gs = [a]
    m = float('inf')
    for y in sorted(set(a)):
        gs = groups(gs, y, k)
        x = find_x(gs, y, k, q)
        if x is None:
            break
        m = min(m, x - y)
    
    print(m)

def find_x(gs, y, k, q):
    xs = []

    for g in gs:
        xs.extend(heapq.nsmallest(len(g) - k + 1, g))
    
    xss = heapq.nsmallest(q, xs)
    if len(xss) < q:
        return None
    
    return xss[-1]

def groups(gs, m, k):
    new_gs = []
    for g in gs:
        new_gs.extend(groups_1(g, m, k))
    return new_gs

def groups_1(a, m, k):
    g = []

    pos = 0
    while pos < len(a):
        i = pos
        while i < len(a) and a[i] < m:
            i += 1
        
        j = i
        while j < len(a) and a[j] >= m:
            j += 1
        
        if j - i >= k:
            g.append(a[i:j])
        
        pos = j
    
    return g

main()

Submission status: Accepted

Solution code:
import heapq

def main():
    n, k, q = map(int, input().split())
    a = tuple(map(int, input().split()))

    m = float('inf')
    for y in sorted(set(a)):
        x = find_x(a, y, k, q)
        if x is None:
            break
        m = min(m, x - y)
    
    print(m)

def find_x(a, y, k, q):
    gs = groups(a, y, k)
    xs = []

    for g in gs:
        xs.extend(heapq.nsmallest(len(g) - k + 1, g))
    
    xss = heapq.nsmallest(q, xs)
    if len(xss) < q:
        return None
    
    return xss[-1]

def groups(a, m, k):
    g = []

    pos = 0
    while pos < len(a):
        i = pos
        while i < len(a) and a[i] < m:
            i += 1
        
        j = i
        while j < len(a) and a[j] >= m:
            j += 1
        
        if j - i >= k:
            g.append(a[i:j])
        
        pos = j
    
    return g

main()

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = [int(x) for x in input().split()]
m = None
for x in a:
    b = []
    c = []
    for y in a:
        if y < x:
            if len(c) >= k:
                c.sort()
                b.extend(c[:len(c) - k + 1])
            c = []
        else:
            c.append(y)
    if len(c) >= k:
        c.sort()
        b.extend(c[:len(c) - k + 1])
    if len(b) >= q:
        b.sort()
        if m is None or m > b[q - 1] - x: m = b[q - 1] - x
print(m)

Submission status: Accepted

Solution code:
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]
S = sorted(A)+[0]
A+=[0]
ans =[]
for i in range(N):
    if S[i]==S[i+1]:
        continue
    mi = S[i]
    L =[]
    kou=[]
    for y in range(N+1):
        if A[y]>=mi:
            kou.append(A[y])
        elif len(kou)<K:
            kou =[]
        else:
            L+=sorted(kou)[:len(kou)-K+1]
            kou =[]
    if len(L)<Q:
        continue
    L.sort()
    ans.append((L[Q-1]-mi))
print(min(ans))

Submission status: Accepted

Solution code:
N,K,Q = map(int, input().split())
A = [int(i) for i in input().split()]
A+=[0]
S = sorted(A)
ans =[]
for i in range(1,N+1):
    if S[i]==S[i-1]:
        continue
    mi = S[i]
    L =[]
    x = 0
    for y in range(N+1):
        if A[y]<mi:
            if (y-x)>=K:
                L += sorted(A[x:y])[:y-x-K+1]
            x = y+1
    if len(L)<Q:
        continue
    L.sort()
    ans.append((L[Q-1]-mi))
print(min(ans))

Submission status: Accepted

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

ans = 10**18
for i in range(N):
    pv = A[i]
    res = []; tmp = []
    for a in A:
        if pv <= a:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                tmp.sort()
                res.extend(tmp[:len(tmp)-K+1])
            tmp = []
    if len(tmp) >= K:
        tmp.sort()
        res.extend(tmp[:len(tmp)-K+1])
    if Q <= len(res):
        res.sort()
        ans = min(ans, res[Q-1]-res[0])
print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
sortedA = sorted(set(A))
ans = []
for v in sortedA:
    C = [[]]
    for i, t in enumerate(A):
        if t < v  and len(C[-1]) > 0 :
            C.append([])
        if t >= v :
            C[-1].append(t)
    tmp = []
    for t in C:
        if len(t) >= K:
            tmp += sorted(t)[:len(t)-K+1]
    tmp.sort()
    if len(tmp) >= Q:
        ans.append(tmp[Q-1] - v)
print(min(ans))

Submission status: Accepted

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() + [-1]
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n+1):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        b = []
        c = 0
        for j in range(n+1):
            if a[j] < mi:
                if j - c >= k:
                    b += sorted(a[c:j])[:j-c-k+1]
                c = j + 1
        if len(b) < q:
            continue
        b.sort()
        t = b[q-1] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, k, q = map(int, raw_input().split())
    a = map(int, raw_input().split())
    d = defaultdict(list)
    for i, x in enumerate(a):
        d[x].append(i)
    a.append(-1)
    ans = 1001001001
    for x in sorted(d.keys()):
        p = 0
        b = []
        s = 0
        for j, y in enumerate(a):
            if y < x:
                if j - p >= k:
                    t = a[p:j]
                    t.sort()
                    b.extend(t[:j-p-k+1])
                p = j + 1
        if len(b) >= q:
            b.sort()
            ans = min(ans, b[q-1] - x)
        else:
            break
    print ans
main()

Submission status: Runtime Error

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import groupby
def resolve():
    n, k, q = map(int, input().split())
    A = list(map(int, input().split()))
    B = sorted(A)

    ans = INF
    for i, m in enumerate(B):
        score = 0
        for key, it in groupby([a >= m for a in A]):
            if key is False:
                continue
            l = sum(1 for _ in it)
            score += max(0, l - k + 1)

        if score >= q:
            ans = min(ans, B[i + q - 1] - m)

    print(ans)
resolve()

Submission status: Runtime Error

Solution code:
#解説参照
n,k,q=map(int, input().split())
*a,=map(int, input().split())
a+=[0]
ans=10**10
for i in range(n):
    ai=a[i]
    tmp=[10**10]##15行目でtmp[:0]になるから
    tmp2=[]
    for j in range(n+1):
        if i==j:
            continue
        if a[j]<ai:
            tmp.sort()
            if len(tmp)>=k+1:
                tmp2+=tmp[:-k]
            tmp=[]
        else:
            tmp.append(a[j])
            #print("test",tmp)
    tmp2.sort()
#    print(tmp,tmp2)
    if len(tmp2)>=q-1:    
#        print("test2")
        ans=min(ans,tmp2[q-2]-ai)
print(ans)

Submission status: Runtime Error

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

ans = 10 ** 10
for i, y in enumerate(a):
    li = []
    l = 0
    cnd = []
    for j, x in enumerate(a + [-1]):
        if i == j:
            continue
        if x < y:
            if l - k + 1 >= 0:
                li.sort()
                cnd += li[:l-k+1]
            li = []
            l = 0
        else:
            li.append(x)
            l += 1

    if len(cnd) >= q - 1:
        cnd.sort()
        sub = cnd[q-2] - y
        ans = min(ans, sub)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,K,Q=map(int, input().split())
    *A,=map(int, input().split())

    ans=10**10
    from heapq import heappop, heappush
    A.append(-1)
    for y in A:
        if y==-1: break
        c=[]
        t=[]
        for a in A:
            if a >= y:
                heappush(t, a)
            else:
                for _ in range(len(t)-(K-1)):
                    heappush(c, heappop(t))
                t.clear()
        if len(c) < Q: continue
        x=[heappop(c) for _ in range(Q)][-1]
        ans = min(ans, x-y)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k,q = map(int,input().split())
# N: 処理する区間の長さ
N0 = 2**(n-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
a = list(map(int,input().split()))
for i in range(N0):
    data[i+N0] = a[i]
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

ans = []
for i in range(q):
    res = INF
    for i in range(n-k+1):
        v = query(i,i+k)
        if res > v:
            res = v
            ind = i
        
    ans.append(res)
    update(i,INF)
    
        
        
    

print(max(ans) - min(ans))

Submission status: Runtime Error

Solution code:
n,k,q=map(int,input().split())
a=list(map(int,input().split()))
ans=10**10
for y in a:
	t=[[]]
	for i in a:
		if i<y:
			if len(t[-1]):t.append([])
		else:
			t[-1].append(i)
	if len(t[-1])==0:del t[-1]
	co=0
	m=[]
	for i in range(len(t)):
		co+=max(len(t[i])-k+1,0)
		t[i].sort()
		m+=t[i][:-k+1]
	if co<q:continue
	m.sort()
	ans=min(ans,m[q-1]-y)
print(ans)

Submission status: Runtime Error

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

r = Y[Q-1] - Y[0]
for y in X:
    tmp = []
    tmp2 = []
    for x in X:
        if x < y:
            tmp.sort()
            tn = len(tmp)
            if len(tmp) > K-1:
                tmp2 += tmp[:tn-K+1]
                print(tmp, tmp[:tn-K+1])
            tmp = []
            continue
        tmp.append(x)
    tn = len(tmp)
    if tn-K+1 > 0:
        tmp2 += tmp[:tn-K+1]
    tmp2.sort()
    if len(tmp2) >= Q:
        r = min(r, tmp2[Q-1] - y)
print(r)

Submission status: Runtime Error

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

def getMinX(i, y):
    B = [[]]
    for j, a in enumerate(A):
        if i == j:
            continue
        if a < y and len(B[-1]) > 0:
            B.append([])
        if a >= y:
            B[-1].append(a)

    C = []
    for grp in B:
        grp.sort()
        C += grp[:len(grp) - K + 1]
    C.sort()
    return C[Q - 2] if len(C) >= Q - 1 else 10**18

ans = 10**18
for i, y in enumerate(A):
    ans = min(ans, getMinX(i, y) - y)
print(ans)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, k, q = MAP()
a = LIST()
ans = inf
for i in range(n):
    y = a[i]
    c = []
    tmp = 0
    for j in range(n):
        if a[j] < y:
            if tmp <= i < j:
                c.extend(a[tmp:i])
                c.extend(a[i + 1:j])
            else:
                c.extend(a[tmp:j])
            tmp = j + 1
    if tmp <= i < n:
        c.extend(a[tmp:i])
        c.extend(a[i + 1:n])
    else:
        c.extend(a[tmp:n])
    c.sort()
    #print(y, c)
    if len(c) > q - 2 + k - 1:
        ans = min(ans, c[q - 2] - y)
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

N, K, Q = map(int, input().split())
A = [int(i) for i in input().split()]

ret = float('inf')
for i in range(N) :
    l = -1
    for j in range(i, max(-1, i - Q), -1) :
        if A[j] < A[i] :
            l = j
            break
    r = N      
    for j in range(i, min(N, i + Q)) :
        if A[j] < A[i] :
            r = j
            break
    # print(A[i], r, l)
    if r - l - 1 < Q :
        continue
        
    # print('最小値', i, A[i])
    B = A[::]
    B.pop(i)
    # print(B)
    
    C = [-1]
    for j in range(N - 1) :
        if B[j] < A[i] :
            C.append(j)
    C.append(N - 1)
    # print(C)
    
    D = []
    for j in range(len(C) - 1) :
        if C[j+1] - C[j] - 1 >= K :
            D += sorted(B[C[j]+1:C[j+1]])[:C[j+1] - C[j] - K]
    # print(D)
    
    if len(D) >= Q - 1 :
        D.sort()
        ret = min(ret, D[Q-2] - A[i])
        # print(D[Q-2], A[i], ret)
    # print()

if ret == float('inf') :
    while True :
        pass
else :
    print(ret)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

N, K, Q = map(int, input().split())
A = [int(i) for i in input().split()]

ret = float('inf')
for i in range(N) :
    l = 0
    for j in range(i, max(-1, i - Q), -1) :
        if A[j] < A[i] :
            l = j + 1
            break
    r = N - 1        
    for j in range(i, min(N, i + Q + 1)) :
        if A[j] < A[i] :
            r = j - 1
            break
            
    if r - l + 1 < Q :
        continue
        
    B = A[::]
    B.pop(i)

    C = [-1]
    for j in range(N - 1) :
        if B[j] < A[i] :
            C.append(j)
    C.append(N - 1)

    D = []    
    for j in range(len(C) - 1) :
        if C[j+1] - C[j] - 1 >= K :
            D += sorted(B[C[j]+1:C[j+1]])[:C[j+1] - C[j] - K]
    
    if len(D) >= Q - 1 :
        D.sort()
        ret = min(ret, D[Q-2] - A[i])
        
print(ret)

Submission status: Runtime Error

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

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(b) - b for b in B)

# 出力
print(ans)

Submission status: Runtime Error

Solution code:
n, k, q = map(int, input().split())
alist = list(map(int, input().split()))
ans = None
for i, a in enumerate(alist):
  spla = []
  preva = -1
  ailist = alist[:i] + alist[i+1:]
  for j, _a in enumerate(ailist):
    if _a < a:
      spla.append(ailist[preva+1:j])
      preva = j
  if not preva == len(ailist)-1:
    spla.append(ailist[preva+1:])
  conda = []
  for sa in spla:
    if len(sa) >= k:
      conda.extend(list(sorted(sa))[:len(sa)-k+1])
  if len(conda) < q-1:
    continue
  else:
    y = list(sorted(conda))[q-2]
    if ans is None or ans > y - a:
      ans = y - a

print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/arc098/submissions/2581691
from math import inf


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)

Submission status: Runtime Error

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])


#m_key = max(sL,key=lambda x:x[0])[0]
for key,value in sL:
    #if key >= m_key + K:
    #    continue
    f = False
    C = [(i if i >= B[key] else None) for i in A]
    i = 0
    j = 0
    max_value = B[key + Q - 1]
    length = 0
    over_length = 0
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp <= 0:
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if sC[tmp] < max_value:
            length = 0
            break
        over_length = len([i for i in sC[:tmp]if i > max_value])
        length += tmp
        i = j +1
    if length - over_length >= Q:
        f = True
            
    if f:
        print(value)
        exit()
    #m_key = min(m_key,key)

print(L[0][1])

Submission status: Runtime Error

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()

m_key = max(sL,key=lambda x:x[0])
for key,value in sL:
    if key >= m_key + K:
        continue
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            tmp_length = 1
            for j in range(a_index-1,-1,-1):
                if j < 0:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] <= b_value:
                    continue
                tmp_length += 1
                if tmp_length >= K:
                    break
            tmp_length -= 1
            for j in range(a_index+1,N):
                if j > N-1:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] < b_value:
                    continue
                length += 1
                if length >= K:
                    break
            length += tmp_length
            if length >= K:
                count += 1
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()
    m_key = min(m_key,key)
    

print(L[0][1])

Submission status: Runtime Error

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_value in B[key:key+Q]:
        a_index = a.index(b_value)
        length = 1
        for j in range(a_index-1,a_index-K,-1):
            if j < 0:
                break 
            if A[j] < b_value:
                break
            length += 1
        for j in range(a_index+1,a_index+K):
            if j > N-1:
                break 
            if A[j] < b_value:
                break
            length += 1
        if length < K:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Runtime Error

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
for key,value in sL:
    f = True
    for b_value in B[key:key+Q]:
        a_index = a.index(b_value)
        length = 1
        for j in range(a_index-1,a_index-K,-1):
            if j < 0:
                break 
            if A[j] < b_value:
                break
            length += 1
        for j in range(a_index+1,a_index+K):
            if j > N-1:
                break 
            if A[j] < b_value:
                break
            length += 1
        if length < K:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):
    ans = sys.maxsize
    for i in range(N):
        x = A[i]
        s = 0
        yc = []
        for j in range(N):
            if A[j] < x or i == j:
                for c in sorted(A[s:j])[:len(A[s:j]) - Q + 2]:
                    bisect.insort(yc, c)
                s = j + 1
        else:
            for c in sorted(A[s:])[:len(A[s:]) - Q + 2]:
                bisect.insort(yc, c)

        if len(yc) > Q - 2:
            # print(yc, yc[Q - 2], x, yc[Q - 2] - x)
            ans = ans if ans < yc[Q - 2] - x else yc[Q - 2] - x

    return ans


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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]
    bis = list(range(i))
    d = 0
    for ai in range(i, i + q):
        ok = True
        for bi in bis:
            if abs(a[bi][1] - a[ai][1]) < k:
                bis.append(ai)
                ok = False
                con = False
                d += 1
                if i + q + d - 1 < n:
                    mi = a[q + i + d - 1][0] - a[i][0]
                    if mi < m:
                        con = True
                break
        if con: continue
        break
    if ok:
        m = mi
print(m)

Submission status: Runtime Error

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+1)
for k in range(N-K-Q+1):
  c[k] = b[k + Q - 1] - b[k]
d = functools.reduce(lambda x,y:min(x,y),c)
print(d)

Submission status: Runtime Error

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]
    bis = list(range(i))
    for ai in range(i, i + q):
        ok = True
        for bi in bis:
            if abs(a[bi][1] - a[ai][1]) < k:
                bis.append(ai)
                ok = False
                con = False
                if i + q < n:
                    mi = a[q + i][0] - a[i][0]
                    if mi < m:
                        con = True
                break
        if con: continue
        break
    if ok:
        m = mi
print(m)

Submission status: Runtime Error

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+1)
for k in range(N-K-Q+1):
  c[k] = b[k + Q - 1] - b[k]
print(c)
d = functools.reduce(lambda x,y:min(x,y),c)
print(d)

Submission status: Runtime Error

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[:K] = 1
    elif j >= N - K:
        luck_flag[-K:] = 1
    else:
        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 = lii()
    A = lii()
    Asort = sorted(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):
        luck_ix.append(ix[i])
        bisect.insort(luck_ix, ix[i])
        luck_flag = manage_luck_flag(luck_flag, ix[i], K)

        cnt = n_removable(N, luck_ix, K)
        # print(i, cnt)
        j = i+Q

        # print(luck_flag)
        while luck_flag[ix[j]] == 1 and j < N:
            j += 1
            if j == N:
                return diff

        if Q > cnt:
            return diff

        # print(i, cnt)
        diff = min(diff, Asort[j] - Asort[i+1])

    return diff

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

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[:K] = 1
    elif j >= N - K:
        luck_flag[-K:] = 1
    else:
        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 = lii()
    A = lii()
    Asort = sorted(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):
        luck_ix.append(ix[i])
        bisect.insort(luck_ix, ix[i])
        luck_flag = manage_luck_flag(luck_flag, ix[i], K)

        cnt = n_removable(N, luck_ix, K)
        # print(i, cnt)
        j = i+Q

        print(luck_flag)
        while luck_flag[ix[j]] == 1 and j < N:
            j += 1
            if j == N:
                return diff

        if Q > cnt:
            return diff

        # print(i, cnt)
        diff = min(diff, Asort[j] - Asort[i+1])

    return diff

if __name__ == '__main__':
    print(main())