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:
N, K, Q = map(int, input().split())
A = [int(i) for i in input().split()]

def solve() :
    if Q == 1 : return min(A)
        
    ret = float('inf')
    for i in range(N) :
        l = -1
        for j in range(i, max(-1, i - K), -1) :
            if A[j] < A[i] :
                l = j
                break
        r = N      
        for j in range(i, min(N, i + K)) :
            if A[j] < A[i] :
                r = j
                break
                
        if r - l - 1 < K :
            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])

    return ret
    
print(solve())

Submission status: Wrong Answer

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

def solve() :
    if Q == 1 : return min(A)
        
    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()

    return ret
    
print(solve())

Submission status: Wrong Answer

Solution code:
from itertools import*
N,K,Q,*A=map(int,open(0).read().split())
s=sorted
print(min((s(sum((v[:1-K or-1]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y))),[]))[Q-1:]+[2e9])[0]-Y for Y in A))

Submission status: Wrong Answer

Solution code:
from itertools import*
N,K,Q,*A=map(int,open(0).read().split())
s=sorted
print(min(s(sum((v[:max(0,len(v)-K+1)]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y))),[])[Q-1:]+[2e9])[0]-Y for Y in A))

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
A_sorted = sorted(A)
ans = 10**10
for m in A_sorted:
    lists = []
    tmp = []
    for a in A:
        if a<m:
            lists.append(tmp)
            tmp = []
        else:
            tmp.append(a)
    lists.append(tmp)
    
    res = []
    for l in lists:
        length = len(l)
        if length<K:
            continue
        l.sort()
        res+=l[:length-K+1]
    if len(res)>=Q:
        ans = min(ans, res[Q-1]-m)
print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

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

nA = sorted(A)
d = []
for i in range(N):
    l = N+1
    r = N+1
    for j in range(i)[::-1]:
        if A[j] < A[i]:
            l = i - j
            break
    for j in range(i, N):
        if A[j] < A[i]:
            r = j - i
            break
    d.append(min(l, r))

ans = inf

for i in range(N-(Q-1)):
    Y = nA[i]
    X = nA[i+Q-1]
    if d[i] > K:
        ans = min(ans, X - Y)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k,q=map(int,input().split())
arr=list(map(int,input().split()))
arr2=sorted(arr)
ans=10**18
m=arr2[0]
for val in arr:
  tmp=[]
  vals=[]
  for i in range(n):
    if arr[i]>=val:
      tmp.append(arr[i])
    else:
      if len(tmp)>=k:
        tmp=sorted(tmp)
        vals.extend(tmp[:len(tmp)-k+1])
        tmp=[]
  if len(tmp)>=k:
    tmp=sorted(tmp)
    vals.extend(tmp[:len(tmp)-k+1])
  if len(vals)<q:
    continue
  else:
    vals=sorted(vals)
    ans=min(ans,vals[q-1]-vals[0])
print(ans)

Submission status: Wrong Answer

Solution code:
def slide_min(tl,ql,val):
  res=[0]*(tl-ql+1)
  q=[0]*tl
  s=0
  t=0
  for i in range(0,tl):
    while s<t and val[q[t-1]]>=val[i]:
      t-=1
    q[t]=i
    t+=1
    if (i-ql+1)>=0:
      res[i-ql+1]=q[s]
      if q[s]==(i-ql+1):
        s+=1
  return res

n,k,q=map(int,input().split())
arr=list(map(int,input().split()))
val=[]
for _ in range(q):
  cond=slide_min(n,k,arr)
  tmp=[10**10,0]
  for i in range(n-k+1):
    num=arr[cond[i]]
    if num<tmp[0]:
      tmp[0]=num
      tmp[1]=cond[i]
  val.append(tmp[0])
  n-=1
  arr=arr[:tmp[1]]+arr[tmp[1]+1:]
print(max(val)-min(val))

Submission status: Wrong Answer

Solution code:
def solve(N, K, Q, As, X):
    mins = []
    tmp = []
    for A in As:
        if A >= X:
            tmp.append(A)
        else:
            if len(tmp) >= K:
                tmp.sort()
                mins.extend(tmp[:len(tmp)-K+1])
                tmp = []
    if len(tmp) >= K:
        tmp.sort()
        mins.extend(tmp[:len(tmp)-K+1])

    if len(mins) < Q:
        return None
    mins.sort()
    taken = mins[:Q]
    return taken[-1] - taken[0]


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

ans = -1
for A in As:
    cand = solve(N, K, Q, As, A)
    if cand is not None and (ans == -1 or ans > cand):
        ans = cand

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

N,K,Q = map(int,input().split())
A = [int(x) for x in input().split()] # 大小逆にする。

# 通行止めを削除していって、区間をマージしていく
# 右端・左端が相互参照できるようにしておく
R_to_L = [None] * (N+10)
L_to_R = [None] * (N+10)
# 区間の左端に、残すK-1個のheapを入れる
rest = [[] for _ in range(N+10)]

from_max = sorted(enumerate(A), key = lambda x: x[1], reverse=True)

INF = 10 ** 18
get_reverse = [-INF] * Q

def push_K(arr,x):
    if len(arr) < K-1:
        heappush(arr,x)
    else:
        y = heappushpop(arr,x)
        # y が獲得できるようになる
        heappushpop(get_reverse, -y)

answer = INF
for i,x in from_max:
    left = R_to_L[i-1]
    right = L_to_R[i+1]
    # x 自身が採用できるか
    if left is None:
        left = i
        rest[left].append(x)
    else:
        push_K(rest[left],x)
    if right is None:
        right = i
    else:
        # merge
        for r in rest[i+1]:
            push_K(rest[left],r)
    R_to_L[right] = left
    L_to_R[left] = right
    score = -get_reverse[0] - x
    if answer > score:
        answer = score

print(answer)

Submission status: Wrong Answer

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

result = 100000000000
for j in range(n):
    li = [[]]
    for i in range(n):
        if a[j] <= a[i]:
            li[-1].append(a[i])
        else:
            li.append([])
    ans = []
    for li_ele in li:
        if len(li_ele) <= k:
            continue
        else:
            tmp = sorted(li_ele)
            ans = ans + tmp[0:len(li_ele)-k+1]
    ans = sorted(ans)
    if len(ans) >= q:
        result = min(ans[q-1] - a[j], result)
print(result)

Submission status: Wrong Answer

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

from collections import deque

def slide_min(a):
    q = deque()
    max_num = 0
    max_ind = 0
    for i in range(len(a)):
        while q and a[q[-1]] >= a[i]:
            q.pop()
        q.append(i)
        if i - k + 1 >= 0:
            if max_num < a[q[0]]:
                max_num = a[q[0]]
                max_ind = q[0]
            if q[0] == i - k + 1:
                q.popleft()
    return max_ind

# 小さいものをとっていく場合
b = sorted(a)
ans1 = b[q-1] - b[0]


# 大きいものをとっていく場合
li = []
for i in range(q):
    remove_ind = slide_min(a)
    li.append(a[remove_ind])
    del a[remove_ind]
ans2 = max(li) - min(li)

print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
def main():
    N, K, Q = map(int, input().split())
    A = list(map(int, input().split()))
    ans = float("inf")
    for X in A:
        targets = []
        target = []
        for a in A:
            if a >= X:
                target.append(a)
            elif a < X:
                if len(target) >= K:
                    target.sort()
                    targets += target[:len(target)-(K-1)]
                target = []
        target.sort()
        targets += target[:len(target)-(K-1)]
        targets.sort()
        if len(targets) >= Q:
            ans = min(targets[Q-1] - targets[0], ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
N, K, Q = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
sA = sorted(set(A))
A += [-1]
ans = float('inf')

for amin in sA:
    cand = []
    fr = 0
    to = -1
    for i in range(N + 1):
        a = A[i]
        if a >= amin:
            if fr == -1:
                fr = i
        elif a < amin and fr >= 0:
            cand += sorted(A[fr:i])[:max(0, i - fr - K + 1)]
            fr = -1
    if len(cand) < Q:
        break
    ans = min(ans, cand[Q - 1] - amin)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, K, Q = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
ans = float('inf')
for amin in sorted(set(A)):
    cand = []
    dp = []
    for i in range(N):
        a = A[i]
        if a >= amin:
            heapq.heappush(dp, a)
        if len(dp) and (a < amin or i == N - 1):
            m = len(dp) - K + 1
            for _ in range(m):
                heapq.heappush(cand, heapq.heappop(dp))
    y = float('inf')
    if len(cand) < Q:
        break
    for _ in range(Q):
        y = heapq.heappop(cand)
    ans = min(ans, y - amin)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N, K, Q = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
ans = float('inf')
for amin in sorted(set(A)):
    cand = []
    dp = []
    for i in range(N):
        a = A[i]
        if a >= amin:
            heapq.heappush(dp, a)
        if len(dp) and (a < amin or i == N - 1):
            m = len(dp) - K + 1
            for _ in range(m):
                heapq.heappush(cand, heapq.heappop(dp))
    y = float('inf')
    if len(cand) >= Q:
        for _ in range(Q):
            y = heapq.heappop(cand)
        ans = min(ans, y - amin)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
D = set()
for i in range(N):
    D.add(A[i])

D = list(D)
ans = float('inf')
tmp = []
for Y in D:
    T = []
    for j in range(N):
        if A[j] >= Y:
            tmp.append(A[j])
        else:
            if len(tmp) < K:
                tmp = []
            else:
                tmp = sorted(tmp)
                T += tmp[:len(tmp) - K + 1]
                tmp = []

    if len(T) >= Q:
        T = sorted(T)
        T = T[:Q]
        ans = min(ans, T[-1] - T[0])

print(ans)

Submission status: Wrong Answer

Solution code:


n, k, q = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#print(a)
ans = float("inf")
for i in range(n):
    y = a[i]

    c = []
    c_k = []
    for j in range(n):
        if a[j] >= y:
            c_k.append(a[j])
        else:
            c.append(c_k)
            c_k = []
    else:
        c.append(c_k)

    d = []
    for j in c:
        if len(j) >= k:
            j.sort()
            for l in range(len(j)-k+1):
                d.append(j[l])

    if len(d) >= q:
        ans = min(ans, d[q-1] - d[0])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, 0
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+1)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, 0
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+1)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok += 1
	ok = min(n-q, ok)
	if k == 1:
		ok = n-q
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, 0
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+1)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, 0
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+1)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok = min(n-q, ok)
	if k == 1:
		ok = n-q
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, -1
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+2)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, -1
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+2)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok = min(n-q, ok)
	if k == 1:
		ok = n-q
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, -1
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+2)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, -1
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+2)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok = min(n-q, ok)
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, 1
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+2)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, 1
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+2)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok = min(n-q, ok)
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
c = Counter(a)
def avoidable(x):
	if c[b[x]] == 1:
		cnt, tmp = 0, 0
		for i in range(n):
			if a[i] > b[x]:
				tmp += 1
			else:
				cnt += max(0, tmp-k+1)
				tmp = 0
		cnt += max(0, tmp-k+1)
		if cnt < q:
			return False
		else:
			return True
	else:
		ok = False
		for j in range(n):
			if a[j] != b[x]:
				continue
			cnt, tmp = 0, 0
			for i in range(n):
				if a[i] >= b[x] and i != j:
					tmp += 1
				else:
					cnt += max(0, tmp-k+1)
					tmp = 0
			cnt += max(0, tmp-k+1)
			if cnt >= q:
				ok = True
				break
		if ok:
			return True
		else:
			return False

if not avoidable(0):
	#print("hoge")
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	ok = min(n-q, ok)
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

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

def avoidable(x):
	cnt = 0
	tmp = 0
	for i in range(n):
		if a[i] > b[x]:
			tmp += 1
		else:
			cnt += max(0, tmp-k+1)
			tmp = 0
	cnt += max(0, tmp-k+1)
	if x<q:
		return False
	else:
		return True

if not avoidable(0):
	print(b[q-1] - b[0])
else:
	ok, ng = 0, n
	while ng-ok > 1:
		ind = (ok+ng)//2
		if avoidable(ind):
			ok = ind
		else:
			ng = ind

	ans = 10**10
	while ok >= 0:
		ans = min(ans, b[ok+q-1] - b[ok])
		ok -= 1
	print(ans)

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = sorted(map(int,input().split()))
a,b = 10**9,0
for i in range(Q):
    a = min(a,A[0])
    b = max(b,A[0])
    A.pop(0)
    print(b,a)
print(b-a)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools, heapq
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

n,k,q = [int(i) for i in input().split()]
a = [int(i) for i in input().split()] + [0]
aa = sorted(a)

ans = 10**9+1
mmm = 0
for i,m in enumerate(aa):
    if mmm == m: continue
    hh = [] 
    mae = 0
    for j,aj in enumerate(a):
        if aj < m:
            h=a[mae:j]
            heapq.heapify(h)
#            print(h,"h")
            for _ in range(j-mae-k+1):
                hh.append(heapq.heappop(h))
            mae = j
    mmm = m
    
#    print(hh)
    if len(hh) < q: break
    else:
        hh.sort()
        ans = min(ans, hh[q-1]-hh[0])
            
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = [int(a) for a in input().split()]

minSub = 10**10
for i in range(N):
    X = A[i]
    start = False
    end = 0
    subarray = []
    while  end < N:
        if not start and A[end] >= X:
            start = end
            smallarray = [A[end]]
        elif A[end] >= X: smallarray.append(A[end])
        elif start and A[end] < X:
            if end - start >= K:
                smallarray.sort()
                for j in range(len(smallarray) - K + 1):
                    subarray.append(smallarray[j])
            start = False
        end += 1
    if start:
        if end - start >= K:
            smallarray.sort()
            for j in range(len(smallarray) - K + 1):
                subarray.append(smallarray[j])
    if len(subarray) < Q: continue
    else: 
        subarray.sort()
        minSub = min(minSub, subarray[Q-1] - subarray[0])
print(minSub)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = [int(a) for a in input().split()]

minSub = 1000000000
for i in range(N):
    X = A[i]
    left, right = i, i
    subarray = [X]
    for j in reversed(range(i)):
        if A[j] < X:
            left = j+1
            break
        else: subarray.append(A[j])
    for j in range(i+1, N):
        if A[j] < X:
            right = j-1
            break
        else: subarray.append(A[j])
    if len(subarray) < Q + K - 1: continue
    else: 
        subarray.sort()
        minSub = min(minSub, subarray[Q-1] - subarray[0])
print(minSub)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N, K, Q = map(int, input().split())
A = [int(a) for a in input().split()]

minSub = 1000000000
for i in range(N):
    X = A[i]
    left, right = i, i
    for j in reversed(range(i)):
        if A[j] < X:
            left = j+1
            break
    else: left = 0
    for j in range(i+1, N):
        if A[j] < X:
            right = j-1
            break
    else: right = N-1
    if right - left + 1 < Q + K - 1: continue
    else: 
        subarray = deepcopy(A[left:right+1])
        subarray.sort()
        minSub = min(minSub, subarray[Q-1] - X)
print(minSub)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = [int(a) for a in input().split()]

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

Submission status: Wrong Answer

Solution code:
N,K,Q=map(int,input().split())
A=sorted([int(i) for i in input().split()])
print(A[Q-1]-A[0])

Submission status: Wrong Answer

Solution code:
n,k,q = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
cr = []
for i in range(q):
    br = []
    for j in range(len(ar)-k+1):
        br.append(min(ar[j:j+k]))
    cr.append(min(br))
    del ar[ar.index(min(br))]
print(max(cr)-min(cr))

Submission status: Wrong Answer

Solution code:
N, K, Q = [int(i) for i in input().split()]
A = [(int(v),i) for i,v in enumerate(input().split())]
A.sort()
B = [0]*(N)
for i in range(N):
    B[A[i][1]] = i
C = [A[B[i]][0] for i in range(N)]
Candi = set(range(N))
ctr = 0
ans = []
while len(Candi) >= Q:
    T = sorted(Candi)
    ans.append((list(T)[0],list(T)[Q-1]))
    x = B.index(ctr)
    Candi = Candi - set(B[x-K+1:x+K])
    ctr += 1
print(min([A[j][0]-A[i][0] for i,j in ans]))

Submission status: Wrong Answer

Solution code:
N, K, Q = [int(i) for i in input().split()]
A = [(int(v),i) for i,v in enumerate(input().split())]
A.sort()
B = [0]*(N)
for i in range(N):
    B[A[i][1]] = i
C = [A[B[i]][0] for i in range(N)]
Candi = set(range(N))
ctr = 0
ans = []
while len(Candi) >= Q:
    ans.append((list(Candi)[0],list(Candi)[Q-1]))
    x = B.index(ctr)
    Candi = Candi - set(B[x-K+1:x+K])
    ctr += 1
print(min([A[j][0]-A[i][0] for i,j in ans]))

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
import bisect

N, K, Q = inpl()
A = inpl()
rng = [0, N+1]
B = [(i+1, v) for i, v in enumerate(A)]
B = sorted(B, key = lambda x: x[1])
maxi = max(rng[-1] - rng[0] - K, 0)
i = 0
while maxi >= Q:
    j = bisect.bisect_left(rng,B[i][0])
    bisect.insort_left(rng, B[i][0])
    maxi += max(rng[j+1]-rng[j]-K, 0)\
    + max(rng[j]-rng[j-1]-K, 0)\
    - max(rng[j+1]-rng[j-1]-K, 0)
    i += 1
D = len(rng) - 2
ans = float('inf')
for i in range(D):
    ans = min(ans, B[Q+i-1][1]-B[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
N,K,Q = a = map(int,input().split())
a = list(map(int,input().split()))
inf = 10**10
ans = inf
for i in range(N):
    small = a[i]
    seq = []
    seqq = []
    for j in range(N):
        if a[j] < small:
            seq.append(seqq)
            seqq = []
        else:
            seqq.append(a[j])
    seq.append(seqq)
    aaa = []
    for s in seq:
        if len(s)>=K:
            s.sort()
            aaa += s[:len(s)-K+1]
    if len(aaa)>=Q:
        aaa.sort()
        ans = min(ans,aaa[Q-1]-aaa[0])
        print(i,a[i],aaa,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
def list_split(arr, x):
    ret = []
    d = []
    for v in arr:
        if v >= x:
            d.append(v)
        elif d:
            ret.append(d)
            d = []
    else:
        if d:
            ret.append(d)
    return ret

ans = 10 ** 9
for x in sorted(A):
    y = []
    for arr in list_split(A, x):
        la = len(arr)
        if la > K:
            y += sorted(arr)[:min(la - K + 1, Q)]
    if len(y) >= Q:
        ans = min(ans, sorted(y)[Q - 1] - x)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k,q = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
ans = 10**9
for i in a:
	p,s,f = [],0,1
	for j in range(n):
		if a[j]>=i and f:
			s,f = j,0
		elif a[j]<i and f-1:
			if j-s>=k:
				for j2 in sorted(a[s:j])[:j-s-k+1]: p.append(j2)
			f = 1
	if n-s>=k:
		for j2 in sorted(a[s:n])[:n-s-k+1]: p.append(j2)
	if len(p)>=q: ans = min(ans,sorted(p)[q-1]-i)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K,Q=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
print(A[Q-1]-A[0])

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:
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

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

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

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

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:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
    d_temp.append(sub_temp)
    sub_temp = list()

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a.sort()

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

#print(ans)

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)
        li = list()
 
    d = list()
    a = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li = sorted(li)
            a.extend(li[0:len(li) - k + 1])
 
    a.sort()
 
    if len(a) >= q:
        ans = min(a[q - 1] - a[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()))
 
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)
        li = list()
 
    d = list()
    a = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li.sort()
            a.extend(li[0:len(li) - k + 1])
 
    a.sort()
 
    if len(a) >= q:
        ans = min(a[q - 1] - a[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()))

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


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

  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub.sort()
      a.extend(sub[0:len(sub)-K+1])
  a.sort()
  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

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:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
  d = list()
  a = list()

  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub.sort()
      a.extend(sub[0:len(sub)-K+1])
  a.sort()
  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)