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()))
ans = float('inf')
for a in A: # YがA
    X = []
    Now = []
    for b in A:
        if b >= a:
            Now.append(b)
        else:
            if len(Now) < K:
                Now = []
            else:
                Now.sort()
                X += Now[:len(Now) -K + 1]
    if len(Now) >= K:
        Now.sort()
        X += Now[:len(Now) - K + 1]
    if len(X) < Q:
        continue
    else:
        X.sort()
        x = X[Q-1]
        ans = min(ans, x - a)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for a in A: # YがA
    X = []
    Now = []
    for b in A:
        if b >= a:
            Now.append(b)
        else:
            if len(Now) < K:
                Now = []
            else:
                Now.sort()
                X += Now[:len(Now) -K + 1]
    if len(Now) >= K:
        Now.sort()
        X += Now[:len(Now) - K + 1]
    if len(X) < Q:
        continue
    else:
        x = X[Q-1]
        ans = min(ans, x - a)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A[:])
ans = B[Q-1]-B[0]
for i in range(N-(K+Q-1)+1):
    B = A[i:i+K+Q-1]
    bmin = min(B)
    bmax = max(B)
    ans = min(ans,bmax-bmin)
print(ans)

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:
def main(n,k,q,x):
    ret=float('inf')
    for i,xi in enumerate(x):
        c=[]
        tmp=[]
        for y in x:
            if y<xi:
                if len(tmp)>=k:
                    tmp.sort()
                    for j in range(len(tmp)-k+1):
                        c.append(tmp[j])
                    tmp=[]
            else:tmp.append(y)
        if len(tmp)>=k:
            tmp.sort()
            for j in range(len(tmp)-k+1):
                c.append(tmp[j])
            tmp=[]
        c.sort()
        if len(c)>=q:ret=min(ret,c[q-1]-c[0])
    return ret

#n=int(input())
#a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
n,k,q=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,k,q,x))

Submission status: Wrong Answer

Solution code:
def main(n,k,q,x):
    ret=float('inf')
    for i,xi in enumerate(x):
        c=[]
        tmp=[]
        for y in x:
            if y<xi:
                if len(tmp)>=k:
                    tmp.sort()
                    for j in range(len(tmp)-k+1):
                        c.append(tmp[j])
                    tmp=[]
            else:tmp.append(y)
        if len(tmp)>=k:
            tmp.sort()
            for j in range(len(tmp)-k+1):
                c.append(tmp[j])
            tmp=[]
        c.sort()
        print(xi,c)
        if len(c)>=q:ret=min(ret,c[q-1]-c[0])
    return ret

#n=int(input())
#a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
n,k,q=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,k,q,x))

Submission status: Wrong Answer

Solution code:
def main(n,k,q,x):
    ret=float('inf')
    for i,xi in enumerate(x):
        c=[]
        tmp=[]
        for y in x:
            if y<xi:
                if len(tmp)>=k:
                    tmp.sort()
                    for j in range(len(tmp)-k+1):
                        c.append(tmp[j])
                    tmp=[]
            else:tmp.append(y)
        if len(tmp)>=k:
            tmp.sort()
            for j in range(len(tmp)-k+1):
                c.append(tmp[j])
            tmp=[]
        c.sort()
        if len(c)>=q:ret=min(ret,c[q-1]-xi)
    return ret

#n=int(input())
#a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
n,k,q=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,k,q,x))

Submission status: Wrong Answer

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

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:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,k,q=MI()
aa=LI()
pp=list(sorted(set(aa)))

# 最大-最小を返す
def diff(p):
    can=[]
    cur=[]
    for a in aa+[-1]:
        if a<p:
            if len(cur)==n:
                can=cur
                break
            if len(cur)>=k:
                cur.sort()
                can+=cur[:-(k-1)]
            cur=[]
        else:
            cur.append(a)
    if len(can)<q:
        return -1
    can.sort()
    res=can[q-1]-can[0]
    return res

#print(pp)
ans=10**16
for p in pp:
    ret=diff(p)
    if ret==-1:break
    #print(p,ret)
    ans=min(ans,ret)

print(ans)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
ans = 10**9
# k=1(どこでも取り除ける)とき
# k>1では取り除けるかどうか考えるべき
removed = []
def check(removed, k, target):
    # target: 考慮する番号のindex
    if len(removed) == q:
        return True
    r = n-1
    l = 0
    for num in removed:
        if num > target and r > num:
            r = num
        elif num < target and l < num:
            l = num
    # print(removed, k, target, l, r)
    return r-l >= k

for i in range(q):
    removed.append(a.index(b[i]))

if q == 1:
    print(a[0])
else:
    for i in range(n-q+1):
        can_remove = check(removed, k, a.index(b[i+q-1]))
        if can_remove:
            tmp_ans = b[i+q-1]-b[i]
            # print(i, i+q-1, b[i+q-1], b[i], tmp_ans)
            if tmp_ans < ans:
                ans = tmp_ans
        removed.append(a.index(b[i+q-1]))
    print(ans)

Submission status: Wrong Answer

Solution code:
n,k,q=list(map(int,input().split()))
a=list(map(int,input().split()))
sorta=sorted(a)
ans=10**9
for i in sorta:
    A=[]
    l=[]
    flg=1
    for j in a:
      if i>j:
        flg*=-1
      if flg==1:
        l.append(j)
      if flg==-1:
        flg=1
        if len(l)<k:
          l=[]
          continue
        else:
          l.sort()
          A=A+l[:len(l)-k+1]
    if l:
      l.sort()
      A=A+l[:len(l)-k+1]
    if len(A)<q:
      continue
    else:
      A.sort()
      ans=min(ans,A[q-1]-A[0])
print(ans)

Submission status: Wrong Answer

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

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n,k,q=map(int, input().split())
if q==1:
    print(0)
    exit()
*a,=map(int, input().split())
a+=[-1]
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+1]##
            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: Wrong Answer

Solution code:
n,k,q=map(int, input().split())
if q==1:
    print(0)
    exit()
*a,=map(int, input().split())
a+=[-1]
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: Wrong Answer

Solution code:
n,k,q=map(int, input().split())
if q==1:
    print(0)
    exit()
*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: Wrong Answer

Solution code:
n,k,q=map(int,input().split())
A=[int(i) for i in input().split()]

ans=10**10

for m in set(A)|{0}:
    can=[]
    stc=0
    for i in range(n):
        if A[i]<m and i-stc>=k:
            can.extend(sorted(A[stc:i])[:i-stc-k+1])
            stc=i+1
        elif A[i]<m:
            stc=i+1
    i+=1        
    
    if i-stc>=k:
        can.extend(sorted(A[stc:i])[:i-stc-k+1])
    
    if len(can)>=q:
        ans=min(ans,can[q-1]-can[0])
    #print(m,can)

print(ans)
if ans==10**10:
    raise "error"

Submission status: Wrong Answer

Solution code:
n,k,q=map(int,input().split())
A=[int(i) for i in input().split()]

ans=10**10

for m in set(A)|{0}:
    can=[]
    stc=0
    for i in range(n):
        if A[i]<m and i-stc>=k:
            can.extend(sorted(A[stc:i])[:i-stc-k+1])
            stc=i+1
        elif A[i]<m:
            stc=i+1
    i+=1        
    
    if i-stc>=k:
        can.extend(sorted(A[stc:i])[:i-stc-k+1])
    
    if len(can)>=q:
        ans=min(ans,can[q-1]-can[0])
    #print(m,can)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n,k,q = map(int,input().split())
a = list(map(int,input().split()))
if q == 1:
  print(0)
  exit()
ls = [-1,n]
b = sorted(((a[i],i) for i in range(n)))
ansls = [b[q-1][0]-b[0][0]]
space = [n]
qc = q
for i,x in enumerate(b):
  if n-i < k+q-1:
    break
  for j in range(i,n):
    idx = bisect.bisect_left(ls,b[j][1])
    if space[idx-1] < k:
      continue
    qc -= 1
    space[idx-1] -= 1
    if qc == 0:
      ansls.append(b[j][0]-x[0])
      break
  ins = bisect.bisect_left(ls,i)
  ls.insert(ins,x[1])
  space = []
  qc = q
  for j in range(1,i+3):
    space.append(ls[j]-ls[j-1]-1)
print(min(ansls))

Submission status: Wrong Answer

Solution code:
import bisect
n,k,q = map(int,input().split())
a = list(map(int,input().split()))
if q == 1:
  print(0)
  exit()
ls = [-1,n]
b = sorted(((a[i],i) for i in range(n)))
ansls = [b[q-1][0]-b[0][0]]
for i,x in enumerate(b):
  ins = bisect.bisect_left(ls,i)
  ls.insert(ins,i)
  space = []
  qc = q-1
  for j in range(1,i+3):
    space.append(ls[j]-ls[j-1]-1)
  for j in range(i+1,n):
    idx = bisect.bisect_left(ls,b[j][1])
    if space[idx-1] < k:
      continue
    qc -= 1
    space[idx-1] -= 1
    if qc == 0:
      ansls.append(b[j][0]-x[0])
      break
print(min(ansls))

Submission status: Wrong Answer

Solution code:
N,K,Q,*A = map(int, open(0).read().split())
ans = 10**10
c = min(A[:K])
for i in range(K,N):
  c = min(c,A[i])
  ls = []
  x = []
  for d in A:
    if d>=c:
      x.append(d)
    else:
      ls.append(x)
      x = []
  ls.append(x)
  m = []
  for x in ls:
    x.sort()
    m += x[:max(len(x)-K+1,0)]
  if len(m)<Q:
    continue
  m.sort()
  y = m[Q-1]
  ans = min(ans,y-c)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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, log, log10
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 debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(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()))
def lcm(a, b): return a * b // gcd(a, b)
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]
debugmode = False

n, k, q = MAP()
a = LIST()
a.sort()
print(a[q - 1] - a[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(A[Q-1] - A[0])

Submission status: Wrong Answer

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

def calc(x):
    grp = [[]]
    for a in A:
        if a < x and len(grp[-1]) > 0:
            grp.append([])
        else:
            grp[-1].append(a)
    L = []
    for g in grp:
        g.sort()
        L.extend(g[:max(0, len(g) - K + 1)])
    L.sort()

    if len(L) < Q or L[0] != x:
        return 10**18
    return L[Q - 1] - x

ans = 10**18
for a in A:
    ans = min(ans, calc(a))
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

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


def main():
    w = sorted(A)
    ans = w[Q-1] - w[0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def find_maximum(y):
  C = [[]]
  for a in A:
    if a < y and len(C[-1]) > 0:
      C.append([])
    else:
      C[-1].append(a)
  cand_x = []
  for Ci in C:
    m = len(Ci)
    if m >= K:
      Ci.sort()
      cand_x += Ci[:m-K+1]
  cand_x.sort()
  if len(cand_x) >= Q and cand_x[0] == y:
    return cand_x[Q-1]
  else:
    return 10**18

ans = 10**18
for a in A:
  x = find_maximum(a)
  ans = min(ans, x-a)

print(ans)

Submission status: Wrong Answer

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

def find_maximum(y):
  C = [[]]
  for a in A:
    if a < y and len(C[-1]) > 0:
      C.append([])
    else:
      C[-1].append(a)
  cand_x = []
  for Ci in C:
    m = len(Ci)
    if m >= K:
      Ci.sort()
      cand_x += Ci[:m-K+1]
  cand_x.sort()
  if len(cand_x) >= Q and cand_x[0] == y:
    return cand_x[Q-1]
  else:
    return float('inf')

ans = float('inf')
for a in A:
  x = find_maximum(a)
  ans = min(ans, x-a)

print(ans)

Submission status: Wrong Answer

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

def find_maximum(y):
  C = [[]]
  for a in A:
    if a < y and len(C[-1]) > 0:
      C.append([])
    else:
      C[-1].append(a)
  cand_x = []
  for Ci in C:
    m = len(Ci)
    if m >= K:
      Ci.sort()
      cand_x += Ci[:m-K+1]
  if len(cand_x) >= Q and cand_x[0] == y:
    cand_x.sort()
    return cand_x[Q-1]
  else:
    return float('inf')

ans = float('inf')
for a in A:
  x = find_maximum(a)
  ans = min(ans, x-a)

print(ans)

Submission status: Wrong Answer

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

def find_maximum(y):
  C = [[]]
  for a in A:
    if a < y and len(C[-1]) > 0:
      C.append([])
    else:
      C[-1].append(a)
  cand_x = []
  for Ci in C:
    m = len(Ci)
    if m >= K:
      Ci.sort()
      cand_x += Ci[:m-K+1]
  if len(cand_x) >= Q:
    cand_x.sort()
    return cand_x[Q-1], cand_x[0]
  else:
    return float('inf'), 0

ans = float('inf')
for a in A:
  x, y = find_maximum(a)
  ans = min(ans, x-y)

print(ans)

Submission status: Wrong Answer

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

r = 10**18
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]
            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: Wrong Answer

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

#X = [(i, x) for i, x in enumerate(X)]
#
#Y = sorted(X, key=lambda x: x[1])

r = Y[Q-1] - Y[0]
for y in Y[1:]:
    tmp = []
    tmp2 = []
    for x in X:
        if x < y:
            tmp.sort()
            tn = len(tmp)
            if tn-K+1 > 0:
                tmp2 += 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: Wrong Answer

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

#X = [(i, x) for i, x in enumerate(X)]
#
#Y = sorted(X, key=lambda x: x[1])

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

Submission status: Wrong Answer

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

#X = [(i, x) for i, x in enumerate(X)]
#
#Y = sorted(X, key=lambda x: x[1])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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()
a.sort()
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()))
A.sort()
print(A[Q-1]-A[0])

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K, Q = MAP()
A = LIST()

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

Submission status: Wrong Answer

Solution code:
from heapq import *

n,k,q = map(int, input().split())
a = list(map(int, input().split()))
num_set = set(a)

def parse(b):
    ret = []
    cnt = 0
    tmp = []
    for ai in a:
        if ai >= b:
            tmp.append(ai)
        else:
            if len(tmp) >= k:
                tmp.sort(reverse=True)
                tmp = tmp[k-1:]
                m = tmp.pop()
                ret.append([m, cnt, tmp])
                cnt += 1
                tmp = []
    else:
        if len(tmp) >= k:
            tmp.sort(reverse=True)
            tmp = tmp[k-1:]
            m = tmp.pop()
            ret.append([m, cnt, tmp])
    return ret

ans = 10**10

for b in num_set:
    heap = parse(b)
    heapify(heap)
    tmp = []
    i = 0
    while i<q and heap:
        x,y,z = heappop(heap)
        tmp.append(x)
        if z:
            x = z.pop()
            heappush(heap, [x,y,z])
        i += 1
    if i == q:
        ans = min(ans, max(tmp)-min(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *

n,k,q = map(int, input().split())
a = list(map(int, input().split()))
num_set = set(a)

def parse(b):
    ret = []
    cnt = 0
    tmp = []
    for ai in a:
        if ai >= b:
            tmp.append(ai)
        else:
            if len(tmp) >= k:
                tmp.sort(reverse=True)
                tmp = tmp[k-1:]
                heapify(tmp)
                ret.append(tmp)
                tmp = []
    else:
        if len(tmp) >= k:
            tmp.sort(reverse=True)
            tmp = tmp[k-1:]
            heapify(tmp)
            ret.append(tmp)
    return ret

ans = 10**10

for b in num_set:
    heap = parse(b)
    heapify(heap)
    tmp = []
    i = 0
    while i<q and heap:
        lis = heappop(heap)
        tmp.append(heappop(lis))
        if lis:
            heappush(heap, lis)
        i += 1
    if i == q:
        ans = min(ans, max(tmp)-min(tmp))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
ta = a + []
res = pow(10, 10)
bs = pow(10, 10)
for x in sorted(set(a)):
  t = [[]]
  for i in range(N):
    if ta[i] == bs:
      if t[-1] != []:
        t.append([])
    else: t[-1].append(a[i])
  tt = []
  for i in range(len(t)):
    t[i].sort()
    for j in range(len(t[i]) - K + 1):
      if t[i][j] != bs:
        tt.append(t[i][j])
  if len(tt) < Q: break
  tt.sort()
  res = min(res, tt[Q - 1] - tt[0])
  #print(res, tt, t)
  for i in range(N):
    if a[i] == x:
      for j in range(i - K + 1, i + K):
        if j in range(N):
          ta[j] = bs
  #print(ta, t)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
ta = a + []
res = pow(10, 10)
bs = pow(10, 10)
for x in sorted(set(a)):
  t = [[]]
  for i in range(N):
    if ta[i] == bs:
      if t[-1] != []:
        t.append([])
    else: t[-1].append(a[i])
  tt = []
  for i in range(len(t)):
    t[i].sort()
    for j in range(Q):
      if j in range(len(t[i]) - K + 1):
        if t[i][j] != bs:
          tt.append(t[i][j])
  if len(tt) < Q: break
  tt.sort()
  res = min(res, tt[Q - 1] - tt[0])
  #print(res, tt, t)
  for i in range(N):
    if a[i] == x:
      for j in range(i - K + 1, i + K):
        if j in range(N):
          ta[j] = bs
  #print(ta, t)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
ta = a + []
res = pow(10, 10)
for x in sorted(a):
  #print(ta, x)
  t = sorted(ta)
  if t[Q - 1] == pow(10, 10): break
  res = min(res, t[Q - 1] - t[0])
  for i in range(N):
    if a[i] == x:
      for j in range(i - K + 1, i + K):
        if j in range(N):
          ta[j] = pow(10, 10)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
ta = a + []
res = pow(10, 10)
for x in sorted(a):
  t = sorted(ta)
  if t[Q - 1] == pow(10, 10): break
  res = min(res, t[Q - 1] - t[0])
  for i in range(N):
    if a[i] == x:
      for j in range(i - K + 1, i + K):
        if j in range(N):
          ta[j] = pow(10, 10)
      break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
res = pow(10, 10)
for x in sorted(a):
  t = sorted(a)
  if t[Q - 1] == pow(10, 10): break
  res = min(res, t[Q - 1] - t[0])
  for i in range(N):
    if a[i] == x:
      for j in range(i - K + 1, i + K):
        if j in range(N):
          a[j] = pow(10, 10)
      break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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:
def examC():
    N = I()
    S = SI()
    E = S.count("E"); W = N-E
    curW = 0; curE = 0
    ans = N-1
    for i in range(N):
        if S[i]=="W":
            curW +=1
        cur = N -1 - (W-curW) - curE
        if S[i]=="E":
            curE +=1
        ans = min(ans,cur)
#        print(cur)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    cur = [0]*21
    k = 0; ans = 0
    flag = True
    for i in range(N):
        for j in range(21):
            if cur[j]>=2:
                a = A[i]
                for l in range(21):
                    if a & (1 << l) == (1 << l):
                        cur[l] -= 1
                continue
        flag = True
        while(k<N):
            a = A[k]
            for j in range(21):
                if a&(1<<j)==(1<<j):
                    if cur[j]>=1:
                        flag = False
                        break
            if flag:
                for j in range(21):
                    if a & (1 << j) == (1 << j):
                        cur[j] += 1
                k +=1
            if not flag:
                break
        ans += k-i
#        print(i,k,ans,cur)
        a = A[i]
        for j in range(21):
            if a & (1 << j) == (1 << j):
                cur[j] -= 1

    print(ans)
    return

def examE():
    N, K, Q = LI()
    A = LI()
    ans = inf
    for i in range(N):
        a = A[i]
        curL = []
        l = 0; r = 0
        while(l<N):
            while(r<N):
                if A[r]<a:
                    break
                r +=1
            if l<r:
                curL.append(A[l:r])
            l = r+1
            r = l
#        print(curL)
        cur = []
        for v in curL:
            if len(v)>=K:
                v.sort()
                for j in range(len(v)-K+1):
                    cur.append(v[j])
#        print(cur)
        if len(cur)>=Q:
            now = cur[Q-1]-cur[0]
            ans = min(ans,now)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

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