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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        for j in range(q-1+i, n):
            t = sa[q-1+i] - sa[i]
            # print(i, t)
            if t >= r:
                break
            c = sorted([_[1] for _ in bb if _[0] <= sa[i]]) + [n]
            e = -1
            g = 0
            for d in c:
                if d - e < 2:
                    e = d
                    continue
                f = d - e - 1
                if f > k:
                    g += f - k
                e = d
            # print('g',g,q)
            if g >= q:
                r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            continue
        t = sa[q-1+i] - sa[i]
        # print(i, t)
        if t >= r:
            continue
        c = sorted([_[1] for _ in bb if _[0] <= sa[i]]) + [n]
        e = -1
        g = 0
        for d in c:
            if d - e < 2:
                e = d
                continue
            f = d - e - 1
            if f > k:
                g += f - k
            e = d
        # print('g',g,q)
        if g >= q:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    bb = sorted([[a[i],i] for i in range(n)])
    b = list(map(lambda x: x[1], bb))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1 or sa[i] == sa[i-1]:
            break
        t = sa[q-1+i] - sa[i]
        # print(i, t)
        if t >= r:
            continue
        c = sorted([_[1] for _ in bb if _[0] <= sa[i]]) + [n]
        e = -1
        g = 0
        for d in c:
            if d - e < 2:
                e = d
                continue
            f = d - e - 1
            if f > k:
                g += f - k
            e = d
        # print('g',g,q)
        if g >= q:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI()
    b = list(map(lambda x: x[1], sorted([[a[i],i] for i in range(n)])))
    sa = sorted(a)
    r = sa[q-1] - sa[0]
    # print(r)
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n):
        if q-1+i > n-1:
            break
        t = sa[q-1+i] - sa[i]
        # print(i, t)
        if t >= r:
            continue
        c = sorted(b[:i]) + [n]
        e = -1
        g = 0
        for d in c:
            if d - e < 2:
                e = d
                continue
            f = d - e - 1
            if f > k:
                g += f - k
            e = d
        # print('g',g,q)
        if g >= q:
            r = t


    return r




print(main())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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]
    data=[-1 for i in range(0,N)]
    for k in range(0,N):
        if Y>A[k]:
            data[k]=0
        elif A[k]>X:
            data[k]=1
        else:
            data[k]=2
    check=0
    stack=0
    count=0
    for k in range(0,N):
        if data[k]==1:
            stack+=1
        elif data[k]==2:
            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: Time Limit Exceeded

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

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)

Submission status: Time Limit Exceeded

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)
        li.sort()
        C += li[:max(m-K+1, 0)]
    # 集めた要素からQ個をクエリで使うので、小さい方からQ番目が使う要素の最大値y
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain, groupby

def main():
    N,K,Q,*A=map(int,open(0).read().split())
    s=sorted
    print(min((s(chain.from_iterable((v[:max(0,len(v)-K+1)]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y)))))[Q-1:]or[2e9])[0]-Y for Y in A))

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby, chain

N,K,Q,*A=map(int,open(0).read().split())
s=sorted
print(min((s(chain.from_iterable((v[:max(0,-~(len(v)-K))]for v in(k*s(v)for k,v in groupby(A,lambda a:a>=Y)))))[Q-1:]or[2e9])[0]-Y for Y in set(A)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

import heapq
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			if len(que) >= k:
				removed += heapq.nsmallest(len(que)-k+1, que)
			que = []
		else:
			que.append(a[i])
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10**30
for x in b:
	removed = []
	que = []
	for i in range(n+2):
		if a[i] < x:
			if len(que) >= k:
				removed += heapq.nsmallest(len(que)-k+1, que)
			que = []
		else:
			que.append(a[i])
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
for b in a:
    i=0
    l=[]
    for j,t in enumerate(a+[-1]):
        if t<b:
            l.extend(s(a[i:j])[::-1][k-1:])
            i=j+1
    l.sort()
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)

Submission status: Time Limit Exceeded

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
for b in a:
    i=[i for i,t in enumerate(a)if t<b]
    l=s(u for t in[s(a[i+1:j])[::-1][k-1:]for i,j in zip([-1]+i,i+[n])]for u in t)
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)

Submission status: Time Limit Exceeded

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
for b in a:
    i=[i for i,t in enumerate(a)if t<b]
    l=s(sum([s(a[i+1:j])[::-1][k-1:]for i,j in zip([-1]+i,i+[n])],[]))
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)

Submission status: Time Limit Exceeded

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

ans = 10 ** 9
for Y in As:
    cands = []
    cs = []
    for A in As + [0]: # 最終要素は番兵
        if A < Y:
            cands += sorted(cs)[:max(0, len(cs) - K + 1)]
            cs = []
        else:
            cs += [A]

    if len(cands) < Q: continue
    X = sorted(cands)[Q - 1]

    ans = min(ans, X - Y)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

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:
            # 要素を取得できないパターン
            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
        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: Time Limit Exceeded

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)

Submission status: Time Limit Exceeded

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    temp = sorted(temp)
    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]
            temp2 = []
        else:
            temp2.append(A[j])
    temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]

    temp = sorted(temp)
    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10**9
for i in range(N):
    temp = []
    temp2 = []
    for j in range(N):
        if A[j] < A[i]:
            temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]
            temp2 = []
        else:
            temp2.append(A[j])
    temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]
    temp = sorted(temp)

    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - A[i])
        
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10**9
for i in range(N):
    temp = []
    temp2 = []
    for j in range(N):
        if A[j] < A[i]:
            temp.append(temp2)
            temp2 = []
        else:
            temp2.append(A[j])
    temp.append(temp2)

    temp2 = temp
    temp = []
    for j in range(len(temp2)):
        temp += sorted(temp2[j])[:min(len(temp2[j]),max(0,len(temp2[j]) - K + 1))]
    temp = sorted(temp)

    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - A[i])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import nsmallest


def add_list(s, t, new_lists, removals):
    l = t - s
    if l >= k:
        removals.extend(nsmallest(l - k + 1, aaa[s:t]))
        new_lists.append((s, t))


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [(0, n)]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for s, t in lists:
        for i, b in enumerate(aaa[s:t]):
            if a > b:
                add_list(s, s + i, new_lists, removals)
                s = s + i + 1
        add_list(s, t, new_lists, removals)
    if len(removals) < q:
        break
    ans = min(ans, nsmallest(q, removals)[-1] - a)
    lists = new_lists

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

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

c = []
for i in range(n):
    b = [[]]
    minimum = a[i]
    num = 0
    for j in range(n):
        if a[j] < minimum:
            num = num + 1
            b.append([])
        else:
            b[num].append(a[j])
    d = []
    for j in range(len(b)):
        if len(b[j]) != 0:
            d.append(b[j])
    removable = []
    for j in range(len(d)):
        if len(d[j]) >= k:
            d[j].sort()
            for l in range(len(d[j]) - k + 1):
                removable.append(d[j][l])
    if len(removable) < q:
        continue
    removable.sort()
    maximum = removable[q - 1]
    c.append(maximum - minimum)
print(min(c))

Submission status: Time Limit Exceeded

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

c = []
for i in range(n):
    b = [[]]
    minimum = a[i]
    num = 0
    for j in range(n):
        if a[j] < minimum:
            num = num + 1
            b.append([])
        else:
            b[num].append(a[j])
    removable = []
    for j in range(len(b)):
        if len(b[j]) >= k:
            b[j].sort()
            for l in range(len(b[j]) - k + 1):
                removable.append(b[j][l])
    if len(removable) < q:
        continue
    removable.sort()
    maximum = removable[q - 1]
    c.append(maximum - minimum)
print(min(c))

Submission status: Time Limit Exceeded

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

c = []
for i in range(n):
    b = [[]]
    minimum = a[i]
    num = 0
    for j in range(n):
        if a[j] < minimum:
            num += 1
            b.append([])
        else:
            b[num].append(a[j])
    removable_count = 0
    for j in range(len(b)):
        removable_count += max(0, len(b[j]) - k + 1)
    if removable_count < q:
        continue
    removable = []
    for j in range(len(b)):
        if len(b[j]) >= k:
            b[j].sort()
            for l in range(len(b[j]) - k + 1):
                removable.append(b[j][l])

    removable.sort()
    maximum = removable[q - 1]
    c.append(maximum - minimum)
print(min(c))

Submission status: Time Limit Exceeded

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

c = []
for i in range(n):
    b = [[]]
    minimum = a[i]
    num = 0
    for j in range(n):
        if a[j] < minimum:
            num = num + 1
            b.append([])
        else:
            b[num].append(a[j])
    flag = True
    removable = []
    for j in range(len(b)):
        if len(b[j]) >= k:
            b[j].sort()
            for l in range(len(b[j]) - k + 1):
                removable.append(b[j][l])
    if len(removable) < q:
        flag = False
    if flag == False:
        continue
    removable.sort()
    maximum = removable[q - 1]
    c.append(maximum - minimum)
print(min(c))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return map(int, input().split())

N, K, Q = inpl()
A = " " + input()
S = sorted(map(int, A.split()))
ans = S[Q-1] - S[0]
S = S[::-1]

while S:
    s = S.pop()
    A = A.replace(" {} ".format(s), " x ")

    OK = 0
    Que = A.split("x")

    tmp = []
    for q in Que:
        tmp.extend(sorted([int(x) for x in q.split()])[::-1][K-1:])
    if len(tmp) < Q:
        break
    tmp = sorted(tmp)
    ans = min(ans, tmp[Q-1] - tmp[0])

print(ans)

Submission status: Accepted

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

ans = 10**18
for x in A:
    B = []
    C = []
    for a in A:
        if a >= x:
            C.append(a)
        else:
            if len(C) >= k:
                C.sort()
                B += C[0:len(C)-k+1]
            C = []
    else:
        if len(C) >= k:
            C.sort()
            B += C[0:len(C)-k+1]
    if len(B) >= q:
        B.sort()
        ans = min(ans, B[q-1]-x)
print(ans)

Submission status: Accepted

Solution code:
def main(n,k,q,x):
    ret=float('inf')
    for xi in 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])
        if len(c)>=q:
            c.sort()
            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: Accepted

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

    ans = INF
    for m in sorted(A):
        C = []
        for key, it in groupby(A, key = lambda a : a >= m):
            if key is False:
                continue
            D = list(it)
            if len(D) >= k:
                D.sort()
                C.append(D[:len(D) - k + 1][::-1])

        if sum(len(a) for a in C) < q:
            continue
        heap = [(C[i].pop(), i) for i in range(len(C))]
        heapify(heap)
        for _ in range(q):
            M, i = heappop(heap)
            if C[i]:
                heappush(heap, (C[i].pop(), i))
        ans = min(ans, M - m)

    print(ans)
resolve()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

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

ans = max(a)
rem = [0] * n
while(True):
    nums = [[]]
    i = 0
    while(i<n):
        if(rem[i]==0):
            heappush(nums[-1],a[i])
        else:
            if(nums[-1]):
                nums.append([])
        i += 1

    mins = []
    for hq in nums:
        while(len(hq) >= k):
            mins.append( heappop(hq) )

    if(len(mins) < q):
        print(ans)
        exit()

    mins.sort()
    y = mins[0]
    x = mins[q-1]
    ans = min(ans, x-y)
    for i,ai in enumerate(a):
        if(ai==y):
            rem[i] = 1

Submission status: Accepted

Solution code:
n,k,q=map(int,input().split())
l=list(map(int,input().split()))
ans=10**10
for i in range(n):
    x=l[i]
    tmp=[]
    z=[]
    for j in range(n):
        if l[j]>=x:
            tmp.append(l[j])
        if l[j]<x or j==n-1:
            tmp.sort()
            if len(tmp)-k+1>0:
                z+=tmp[:len(tmp)-k+1]
            tmp=[]
    z.sort()
    if len(z)>=q:
        ans=min(ans,z[q-1]-x)
print(ans)

Submission status: Accepted

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

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

    b = [[v, i]for i, v in enumerate(a)]
    b.sort()
    index = [0]*n
    for i in range(n):
        index[i] = b[i][1]

    judge = [[] for i in range(n)]
    already = [-1, n]

    for i in range(n):
        
        for j in range(len(already)-1):
            key = a[already[j]+1:already[j+1]]
            if len(key) >= k:
                judge[i].append(key)
        already.append(index[i])
        already.sort()

    ans = 1e9
    for i in range(n):
        if not judge[i]:
            break
        m = b[i][0]
        sub = []
        for values in judge[i]:
            values.sort()
            for j in range(len(values)-k+1):
                sub.append(values[j])
        sub.sort()
        if len(sub) < q:
            break
        M = sub[q-1]
        ans = min(ans, M-m)

    print(ans)


    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,q = list(map(int, input().split()))
a = list(map(int, input().split()))
arg = [(num,i) for i,num in enumerate(a)]
arg.sort()
def sub(x):
    """0,1,...,x-1番目は使わない場合において、X-Yの値
    """
    index = [item[1] for item in arg[:x]]
    index.sort()
    index.append(n)
    vals = []
    prv = 0
    for ind in index:
        if ind-prv>=k:
            vals.extend(sorted(a[prv:ind])[:(ind-prv)-k+1])
        prv = ind+1
        if prv>=n:
            break
    if len(vals)<q:
        return None
    else:
        vals.sort()
        return vals[q-1] - arg[x][0]
ans = float("inf")
for i in range(n):
    res = sub(i)
    if res is not None:
        ans = min(ans, res)
print(ans)