Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 2000

1 \leq K \leq N

1 \leq Q \leq N-K+1

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 ... A_N

Output

Print the smallest possible value of X-Y.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

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

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

451211184



Sample input:
5 3 2
4 3 1 5 2


Sample output:
1

Submission status: Accepted

Solution code:
import 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()
                if k==1:can+=cur
                else: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: Accepted

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

n, k, q = map(int, input().split())
A = list(map(int, input().split())) + [-1]
ans = float("inf")
for a in A:
  L = []
  K = []
  for t in A:
    if t >= a:
      L.append(t)
    else:
      L.sort()
      for c in range(len(L)-k+1):
        K.append(L[c])
      L = []
  K.sort()
  if len(K) < q:
    continue
  else:
    y = K[q-1]
    ans = min(ans, y-a)
print(ans)

Submission status: Accepted

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

ans=10**15
for i in range(n):
    x=a[i]
    y_cand=[]
    lis=[]

    for j in range(n):
        if a[j] < x:
            if len(lis)-k+1 >= 0:
                lis.sort()
                y_cand.extend(lis[:len(lis)-k+1])
            lis=[]
        else:
            lis.append(a[j])

    if len(lis)-k+1 >= 0:
        lis.sort()
        y_cand.extend(lis[:len(lis)-k+1])

    if len(y_cand) >= q:
        y_cand.sort()
        y = y_cand[q-1]
        ans = min(ans,abs(x-y))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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**11]##15行目でtmp[:0]になるから
    tmp2=[ai]
    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=[10**11]###
        else:
            tmp.append(a[j])
            #print("test",tmp)
    tmp2.sort()
#    print(tmp,tmp2)
    if len(tmp2)>=q:    
#        print("test2")
        ans=min(ans,tmp2[q-1]-ai)
print(ans)

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
ans = 10000000000000
for m in a:
    res = []
    l = []
    for x in a:
        if x < m and l:
            if len(l) >= k:
                l.sort()
                for p in l[:len(l) - k + 1]:
                    res.append(p)
            l = []
        elif x >= m:
            l.append(x)
    if l:
        if len(l) >= k:
            l.sort()
            for p in l[:len(l) - k + 1]:
                res.append(p)
    res.sort()
    if len(res) >= q:
        ans = min(ans, res[q - 1] - m)
if ans == 10000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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):
  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,x[1])
  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: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

if q == 1:
    print(0)
    exit()

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

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

print(ans)

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def search(x, K, Q, A):
    cand = []
    i = 0
    while i < len(A):
        tmp = []
        while i < len(A):
            if A[i] >= x:
                tmp.append(A[i])
                i += 1
            else:
                i += 1
                break
        if len(tmp) >= K:
            tmp.sort()
            L = len(tmp) - K + 1
            cand.extend(tmp[:L])

    if len(cand) < Q:
        return - 1
    else:
        return sorted(cand)[Q-1]


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

    if Q == 1:
        return 0

    res = 10**18
    for i, x in enumerate(A):
        rest = A[:i] + A[i + 1:]
        y = search(x, K, Q - 1, rest)
        if y == -1:
            continue
        res = min(res, y - x)
    return res


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

Submission status: Accepted

Solution code:
N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
a=list(set(A))
a.sort()
ans=float("inf")
def condition(i,num):
    if i>a[num]:
        return False
    X=a[num]
    Y=A[i]
    check=0
    stack=0
    count=0
    for k in range(0,N):
        if A[k]>X:
            stack+=1
        elif A[k]>=Y:
            stack+=1
            count+=1
        else:
            t=stack+1-K
            check+=max(min(t,count),0)
            stack=0
            count=0
    t=stack+1-K
    check+=max(min(t,count),0)
    return check>=Q

for i in range(0,N):
    start=0
    end=len(a)-1
    while end-start>1:
        test=(end+start)//2
        if condition(i,test):
            end=test
        else:
            start=test
    if condition(i,start):
        ans=min(ans,a[start]-A[i])
    elif condition(i,end):
        ans=min(ans,a[end]-A[i])
print(ans)

Submission status: Accepted

Solution code:
N,K,Q,*A = map(int, open(0).read().split())
ans = 10**10
for i in range(N-K+1):
  c = min(A[i:i+K])
  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: Accepted

Solution code:
def main():
    def calc_x_y(mi):
        """取り除いた要素の最小値がmiとなるように
        操作をQ回行えるか
        行える -> Q回の操作で取り除いた要素の最大値 - mi
        行えない -> -1
        """

        cont = 0
        removed = []
        for i, x in enumerate(a):
            if x < mi:
                if cont >= K:
                    removed += sorted(a[i - cont:i])[:cont - K + 1]
                cont = 0
                continue
            cont += 1
        else:
            if cont >= K:
                removed += sorted(a[-cont:])[:cont - K + 1]

        if len(removed) >= Q:
            removed.sort()
            return removed[Q - 1] - mi
        else:
            return -1

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

    mi_cands = sorted(set(a))

    ans = 10 ** 9
    for mi in mi_cands:
        res = calc_x_y(mi)
        if ~res:
            ans = min(ans, res)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

def div_by_a(border,dlist):
  divided_list=[]
  div=[]
  for d in dlist:
    if d<border:
      if len(div)>0:
        div.sort()
        divided_list.append(div)
        div=[]
    else:
      div.append(d)
  else:
    if len(div)>0:
      div.sort()
      divided_list.append(div)
      
  return divided_list

answer=10**9
for a in alist:
  divlist=div_by_a(a,alist)
  #print(divlist)
  
  cand_list=[]
  for div in divlist:
    cand_num=max(0,len(div)-K+1)
    cand_list.extend(div[:cand_num])
    
  cand_list.sort()
  #print(cand_list)
  if len(cand_list)>=Q:
    answer=min(answer,cand_list[Q-1]-a)   
    
print(answer)

Submission status: Accepted

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

for a in A:
    candidates = []
    tmp = []
    for b in A:
        if a <= b:
            tmp.append(b)
        else:
            if K > 1:
                for i in sorted(tmp)[:-K+1]:
                    candidates.append(i)
            else:
                for i in sorted(tmp):
                    candidates.append(i)
            tmp = []
    if K > 1:
        for i in sorted(tmp)[:-K+1]:
            candidates.append(i)
    else:
        for i in sorted(tmp):
            candidates.append(i)
    candidates.sort()
    if len(candidates) >= Q:
        ans = min(ans, candidates[Q-1] - a)
print(ans)

Submission status: Accepted

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

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for lb in sorted(A):
    tmp = []
    use = []
    for a in A + [-1]:
        if a >= lb:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                use += sorted(tmp)[:len(tmp)-K+1]
            tmp = []
    if len(use) < Q:
        break
    ans = min(ans, sorted(use)[Q-1] - lb)
print(ans)

Submission status: Accepted

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

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
cannot_use = set([-1])
ans = float('inf')
for i in sorted(A):
    tmp = []
    use = []
    for a in A + [-1]:
        if a not in cannot_use:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                tmp.sort()
                use += tmp[:len(tmp)-K+1]
            tmp = []
    use.sort()
    if len(use) < Q:
        break
    ans = min(ans, use[Q-1] - i)
    cannot_use.add(i)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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([])
        if a >= x:
            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: Accepted

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

Submission status: Accepted

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([])
        if a >= x:
            grp[-1].append(a)
    L = []
    for g in grp:
        g.sort()
        L += 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: Accepted

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

for Y in set(A):
    L = []
    l = []
    
    for i in range(N):
        if A[i]<Y:
            L.append(l)
            l = []
        else:
            l.append(A[i])
    
    L.append(l)
    l2 = []
    
    for l in L:
        if len(l)<=K-1:
            continue
        
        l.sort()
        
        for i in range(len(l)-K+1):
            l2.append(l[i])
    
    if len(l2)<Q:
        continue
    
    l2.sort()
    X = l2[Q-1]
    ans = min(ans, X-Y)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K,Q = LI()
A = LI()

# 最小値を決め打ちすると区間を分割できる

Aval = set(A)
ans = float('inf')
for a in Aval:
    now = []
    mins = []
    num = 0
    for i in range(N):
        if A[i] >= a:
            now.append(A[i])
        else:
            if len(now) >= K:
                now.sort()
                mins.extend(now[:len(now)-K+1])
                num += len(now)-K+1
            now = []
    if len(now) >= K:
        now.sort()
        mins.extend(now[:len(now)-K+1])
        num += len(now)-K+1
    if num >= Q:
        mins.sort()
        if mins[Q-1]-a < ans:
            ans = mins[Q-1]-a

print(ans)

Submission status: Accepted

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:
      if 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 10**18, 0

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

print(ans)

Submission status: Accepted

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)
    tmp.sort()
    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: Accepted

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

def main():
    ans = float("inf")

    # A[i]: 最小値X
    for i in range(N):
        # 最大値Yの候補
        can = []

        # A[left:right]: A[i]以上の連続部分列
        left = 0
        while left < N:
            right = left
            while right < N and A[i] <= A[right]:
                right += 1

            # 連続部分列長
            L = right - left

            tmp = sorted([A[j] for j in range(left, right)])
            can += tmp[:max(0, L - K + 1)]

            left = right + 1
        
        # Q番目に小さいものがYの最小値
        can.sort()
        if len(can) >= Q:
            ans = min(ans, can[Q - 1] - A[i])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def sol(y):
    B = [[]]
    for a in A:
        if a < y and len(B[-1]) > 0:
            B.append([])
        if a >= y:
            B[-1].append(a)

    C = []
    for grp in B:
        grp.sort()
        C += grp[:max(0, len(grp) - K + 1)]
    C.sort()

    return C[Q - 1] - y if len(C) >= Q and C[0] == y else 10**18

ans = 10**18
for y in A:
    ans = min(ans, sol(y))

print(ans)

Submission status: Accepted

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

import heapq
ans = 10**10
A.append(-1)
for y in A:
    if y==-1: break
    p,q=[],[]
    for a in A:
        if a >= y:
            heapq.heappush(p, a)
        else:
            for i in range(max(0,len(p)-(K-1))):
                heapq.heappush(q, heapq.heappop(p))
            p=[]
    if len(q) < Q: continue
    x = -1
    for i in range(Q):
        x = heapq.heappop(q)
    ans = min(ans, x-y)
print(ans)

Submission status: Accepted

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
  c.sort()
  ans=min(ans,c[q-1]-c[0])
print(ans)

Submission status: Accepted

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

ans = INF
# 使う要素の最小値とする値xを全探索
for x in A:
    # 数列Aをx未満の値で区切った数列Bを作る
    B = []
    tmp = []
    for i in range(N):
        if A[i] >= x:
            tmp.append(A[i])
        else:
            B.append(tmp)
            tmp = []
    B.append(tmp)
    # 数列B内の各数列から、使える要素を集める
    C =  []
    for li in B:
        m = len(li)
        if m-K+1 >= 1:
            li.sort()
            C += li[:m-K+1]
    # 集めた要素からQ個をクエリで使うので、小さい方からQ番目が使う要素の最大値y
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)

Submission status: Accepted

Solution code:
n,k,q,*a=map(int,open(0).read().split())
ans=10**18
for y in set(a):
  c=[]
  tmp=[]
  for aa in a:
    if aa>=y:
      tmp.append(aa)
    else:
      if len(tmp)>=k:
        c+=sorted(tmp)[:len(tmp)-k+1]
      tmp=[]
  if len(tmp)>=k:
    c+=sorted(tmp)[:len(tmp)-k+1]
  if len(c)>=q:
    c.sort()
    x=c[q-1]
    ans=min(ans,x-y)
print(ans)

Submission status: Accepted

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

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

ans = 10**10

for b in set(a):
    lis = parse(b)
    if len(lis) < q:
        continue
    lis.sort()
    ans_tmp = lis[q-1] - lis[0]
    ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

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

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

ans = 10**10

for b in set(a):
    lis = parse(b)
    if len(lis) < q:
        continue
    lis.sort()
    ans_tmp = lis[q-1] - lis[0]
    ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

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

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

ans = 10**10

for b in num_set:
    lis = parse(b)
    if len(lis) < q:
        continue
    ans_tmp = sorted(lis)[q-1] - min(lis)
    ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc098/tasks/arc098_c

Nの制約が小さい→O(N**2) ?

小さい方からQこの集合にするのは簡単→最小を含むように範囲を選んでけば良い
重要なのは最小の奴を飛ばして範囲がちぢめられるとき。

→最小値を全探索するのか？

最小値を決め、それ以下の数字を含まないようにできるだけ小さい方からとっていく？

k以下の数字のindexで配列を切る。O(N)
各数字がどこに属しているかを二分探索で小さい方からとっていく？
O(NlogN)

→O(N**2logN)で解ける(ちょっときつくないですか)
各数字が領域差しておくか前処理して置けばO(N**2)で解けるかな

"""

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

ai = []
for i in range(N):
    ai.append([a[i],i])
ai.sort()

ans = ai[Q-1][0]-ai[0][0]

for cant in range(N-Q):

    #0 ~ cantまでのai[i]を取ってはいけない

    rannum = [-1] * (cant+2)
    rannum[0] = 0
    indlis = [0] * N #rannumのindexを指し示す

    for i in range(cant+1):

        na,nind = ai[i]
        indlis[nind] += 1


    for i in range(N):

        if i != N-1:
            indlis[i+1] += indlis[i]

        rannum[indlis[i]] += 1

    #print (rannum , indlis)

    ncat = []
    for i in range(cant+1,N):

        na,nind = ai[i]

        if rannum[indlis[nind]] >= K:
            ncat.append(na)
            rannum[indlis[nind]] -= 1

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

    #print (ncat)
    
print (ans)

Submission status: Accepted

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):
      tt.append(t[i][j])
  #print(tt, t, x)
  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:
      ta[i] = bs
  #print(ta, t)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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

ans = 10**14
for x in Xs:
    Ps = []
    tmp = []
    for a in A:
        if a >= x:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                Ps.append(tmp)
            tmp = []
    if len(tmp) >= K:
        Ps.append(tmp)
    q = []
    for P in Ps:
        P.sort()
        for i, p in enumerate(P):
            q.append(p)
            if len(P)-K-i == 0: break
    if len(q) < Q:
        break
    q.sort()
    ans = min(ans, q[Q-1]-x)

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, K, Q = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


def count(l, r, M):
    # [l, r) から M 以下の数を選べる個数
    ret = 0
    for i in range(l, r):
        ret += A[i] <= M
    return min(r - l - K + 1, ret)


def test(M, lr):
    # M 以下の数を Q 個選べるか
    cnt = 0
    for l, r in lr:
        cnt += count(l, r, M)
        if cnt >= Q:
            return True
    return False


def split(lr, i):
    ret = []
    for l, r in lr:
        if l <= i < r:
            if i - l >= K:
                ret.append((l, i))
            if r - (i + 1) >= K:
                ret.append((i + 1, r))
        else:
            ret.append((l, r))
    return ret


# 座圧して BIT 使えばもっと計算量減らせそう
lr = [(0, N)]

ans = max(A) - min(A)
# 小さい順
idx = argsort(A)
for i in idx:
    # i 番目を最小値とする
    m = A[i]
    if test(m + ans - 1, lr):
        ok = m + ans - 1
        ng = m - 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if test(mid, lr):
                ok = mid
            else:
                ng = mid
        ans = ok - m
    lr = split(lr, i)
    if not lr:
        break
print(ans)