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 = 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.append(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())
As = list(map(int, input().split()))

Bs = [(As[i], i) for i in range(N)]
Bs.sort()

orders = [-1] * N
for order, (B, i) in enumerate(Bs):
    orders[i] = order

ans = float('inf')
for C in range(N - Q - K + 2):
    Nos = [-1] * N
    lens = []
    No = 0
    le = 0
    for i in range(N):
        if orders[i]  < C:
            lens += [le]
            No += 1
            le = 0
        else:
            Nos[i] = No
            le += 1

    lens += [le]

    if lens[Nos[C]] < K: continue

    num = 0
    Y = Bs[C][0]
    for B, i in Bs[C:]:
        if lens[Nos[i]] >= K:
            lens[Nos[i]] -= 1
            num += 1
            if num == Q:
                ans = min(ans, B - Y)
                break

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
b = [None]*(N+2)
x = []

def merge(q1, q2):
    if len(q1) < len(q2):
        q1, q2 = q2, q1
    while q2:
        add(q1, heappop(q2))
    return q1

def add(q, v):
    w = push(q, K-1, v)
    if w:
        push(x, Q, -w)

def push(q, m, v):
    if len(q) < m:
        heappush(q, v)
        return
    return heappushpop(q, v)

r = 10**9
for i in sorted(range(1, N+1), key=lambda x: -a[x-1]):
    if b[i-1] and b[i+1]:
        b[i-1] = b[i+1] = merge(b[i-1], b[i+1])
        add(b[i-1], a[i-1])
    elif b[i-1]:
        add(b[i-1], a[i-1])
        b[i] = b[i-1]
    elif b[i+1]:
        add(b[i+1], a[i-1])
        b[i] = b[i+1]
    else:
        b[i] = [a[i-1]]
    if len(x) == Q:
        r = min(r, -x[0]-a[i-1])
print(r)

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
kotae = float("inf")
for i in range(len(a)-Q+1-K+1):
  kotae = min(kotae,a[i+Q-1]-a[i])
print(kotae)

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:
#!/usr/bin/env python

n, k, q = (int(num) for num in input().rstrip().split(" "))
nums = [int(num) for num in input().rstrip().split(" ")]
nums.sort()
print(nums[q-1] - nums[0])

Submission status: Wrong Answer

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

_min = min(A)
A.sort()
for q in range(Q):
    _max = A.pop(0)
print(_max - _min)

Submission status: Wrong Answer

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

_min = min(A)
A.sort()
for k in range(K):
    _max = A.pop(0)
print(_max - _min)

Submission status: Wrong Answer

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()

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

for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    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 < 1:
            if min(C[i:j]) < max_value:
                count = 0
                break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        if sC[tmp] < max_value:
            count = 0
            break
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

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()

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

for key,value in sL:
    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
    min_OK = False
    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:
            if min(C[i:j]) < max_value:
                length = 0
                break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and sC[0] == B[key]:
            min_OK = True
        if sC[tmp] < max_value:
            length = 0
            break
        length += tmp - len([i for i in sC[:tmp]if i > max_value])
        i = j +1
    f = min_OK and length >= Q
            
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

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()

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

for key,value in sL:
    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
    min_OK = False
    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:
            if min(C[i:j]) < max_value:
                length = 0
                break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and sC[0] == B[key]:
            min_OK = True
        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
    f = min_OK and length - over_length >= Q
            
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

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()

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

for key,value in sL:
    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
    min_OK = False
    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:
            if min(C[i:j]) < max_value:
                length = 0
                break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and sC[0] == B[key]:
            min_OK = True
        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
    f = min_OK and length - over_length >= Q
            
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

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()

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

for key,value in sL:
    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:
            if min(C[i:j]) < max_value:
                length = 0
                break
            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()

print(L[0][1])

Submission status: Wrong Answer

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])[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: Wrong Answer

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])[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: Wrong Answer

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])[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]
    print(key,max_value)
    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: Wrong Answer

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])[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
    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
        if sC[tmp-1] > max_value:
            length = 0
            break
        length += tmp
        i = j +1
    if length >= Q:
        f = True
            
    if f:
        print(value)
        exit()
    m_key = min(m_key,key)

print(L[0][1])

Submission status: Wrong Answer

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])[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
    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
        if sorted(C[i:j])[tmp] < max_value:
            length = 0
            break
        if sorted(C[i:j])[tmp-1] > max_value:
            length = 0
            break
        length += tmp
        i = j +1
    if length >= Q:
        f = True
            

    if f:
        print(value)
        exit()
    m_key = min(m_key,key)
    

print(L[0][1])

Submission status: Wrong Answer

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])[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
    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
        if sorted(C[i:j])[tmp] < max_value:
            length = 0
            break
        length += tmp
        i = j +1
    if length >= Q:
        f = True
            

    if f:
        print(value)
        exit()
    m_key = min(m_key,key)
    

print(L[0][1])

Submission status: Wrong Answer

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])[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
    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
        if sorted(C[i:j])[tmp] < max_value:
            break
        length += tmp
        i = j +1
    if length >= Q:
        f = True
            

    if f:
        print(value)
        exit()
    m_key = min(m_key,key)
    

print(L[0][1])

Submission status: Wrong Answer

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])[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: Wrong Answer

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を更新

m_key = sL[0][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 = key
    

print(L[0][1])

Submission status: Wrong Answer

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を更新

m_key = sL[0][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
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()
    m_key = key
    

print(L[0][1])

Submission status: Wrong Answer

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を更新

m_key = sL[0][0]
for key,value in sL:
    if key > m_key:
        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
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()
    m_key = key
    

print(L[0][1])