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

Solution code:
from heapq import heappush,heappop
N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
ans=float("inf")
for x in A:
    data=[]
    h=[]
    for i in range(N):
        if A[i]>=x:
            heappush(h,A[i])
        else:
            if h:
                data.append(h)
                h=[]
    if h:
        data.append(h)
    lsls=[]
    for h in data:
        for j in range(max(0,len(h)-K+1)):
            lsls.append(heappop(h))
    lsls.sort()
    if len(lsls)>=Q:
        ans=min(ans,lsls[Q-1]-lsls[0])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k, q = LI()
A = LI()


def list_split(arr, x):
    ret = []
    d = []
    for v in arr:
        if v >= x:
            d += [v]
        elif d:
            ret += [d]
            d = []
    else:
        ret += [d]
    return ret


ans = INF
for e in set(A):
    y = []
    for arr in list_split(A, e):
        l = len(arr)
        if l >= k:
            y += sorted(arr)[:min(l - k + 1, q)]
    if len(y) >= q:
        ans = min(ans, sorted(y)[q - 1] - e)



print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k,q = LI()
    a = LI()
    b = [[a[i],i] for i in range(n)]
    b.sort()
    ans = b[q-1][0]-b[0][0]
    l = [-1,n]
    for i in range(1,n):
        l.append(b[i-1][1])
        l.sort()
        if b[i-1][0] == b[i][0]:
            continue
        s = [a[l[i]+1:l[i+1]] for i in range(i+1)]
        c = []
        for si in s:
            si.sort()
            for j in range(len(si)-k+1):
                c.append(si[j])
        if len(c) < q:
            continue
        c.sort()
        m = c[q-1]-c[0]
        if m < ans:
            ans = m
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n, k, q = map(int, input().split())
    a = list(map(int, input().split()))
    c = ct(a).keys()
    a += [0]
    ans = []
    for i in c:
        temp = []
        temp2 = []
        for j in a:
            if j >= i:
                temp2.append(j)
            else:
                if temp2:
                    temp2.sort()
                    if len(temp2) >= k:
                        for l in temp2[:len(temp2)-k+1]:
                            temp.append(l)
                    temp2 = []
        if len(temp) >= q:
            temp.sort()
            ans.append(temp[q-1]-i)
    print(min(ans))


main()

Submission status: Accepted

Solution code:
n , k , q = map(int , input().split())
a = [0] * (n + 1)
b = list(map ( int , input().split()))
for i in range(1 , n + 1):
	a[i] = b[i - 1];
def check( l , r):
	cnt = 0;
	ln = 0;
	res = 0;
	for i in range(1 , n + 1):
		if a[i] < l:
			res += min(cnt , max(0 , ln - k + 1))
			ln = 0;
			cnt = 0;
		else :
			ln += 1;
			if a[i] <= r:
				cnt += 1;
	res += min(cnt , max(0 , ln - k + 1))
	if(res >= q):
		return True;
	return False;						

l = 0;
r = 1000000000;
res = 1000000000;
while(l <= r):
	m = (l + r) // 2;
	ok = 0;
	for i in range(1 , n + 1):
		ok |= check(a[i] - m , a[i]);
	if ok == 1:
		r = m - 1;
		res = m;
	else :
		l = m + 1;
print(res)

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


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

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


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


idx = argsort(A)
used = [False] * N
ans = INF
# 小さい方の値を決め打つ
for min_i in idx:
    groups = [[]]
    for i in range(N):
        if used[i]:
            if groups[-1]:
                groups.append([])
        else:
            groups[-1].append(A[i])
    nums = []
    for group in groups:
        if len(group) >= K:
            group.sort()
            nums += group[:len(group) - K + 1]
    if len(nums) < Q:
        break
    nums.sort()
    ans = min(ans, nums[Q - 1] - nums[0])
    used[min_i] = True
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

import heapq as hp


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

    NUM = sorted(list(set(A)))

    ans = 10**10
    for n in NUM:
        Qs = []
        q = []
        for i in range(N):
            if A[i] < n:
                if q:
                    Qs.append(q)
                    q = []
                continue
            if not q:
                q = [A[i]]
            else:
                hp.heappush(q, A[i])
        if q:
            Qs.append(q)
        P = []
        for q in Qs:
            l = len(q)
            if l < K: continue
            for _ in range(min(Q, l-K+1)):
                v = hp.heappop(q)
                P.append(v)
        if len(P) < Q:
            break
        P.sort()
        ans = min(ans, P[Q-1]-P[0])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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[1e10])[0]-Y for Y in A))

Submission status: Accepted

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e9
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])],[]))[q-1:]
 if l:m=min(m,l[0]-b)
print(m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, K, Q, *A = map(int, open(0).read().split())

    ans = float("inf")
    for Y in set(A):
        C = []
        tmp = []
        for a in A:
            if a >= Y:
                tmp.append(a)
            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)

main()

Submission status: Accepted

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e9
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: Accepted

Solution code:
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e9
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: Accepted

Solution code:
from itertools import*
N,K,Q,*A=map(int,open(0).read().split())
l=len
s=sorted
a=1e9
for Y in set(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: Accepted

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: Accepted

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[:len(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: Accepted

Solution code:
from itertools import groupby, chain
N, K, Q, *A = map(int, open(0).read().split())
ans = float("inf")
for Y in set(A):
    C = sorted(chain.from_iterable(v[:len(v) - K + 1] for v in (sorted(v) for k, v in groupby(A, key=lambda a: a >= Y) if k) if len(v) >= K))
    if len(C) >= Q:
        ans = min(ans, C[Q - 1] - Y)
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, chain

N, K, Q, *A = map(int, open(0).read().split())

ans = float("inf")
for Y in set(A):
    G = (sorted(v) for k, v in groupby(A, key=lambda a: a >= Y) if k)
    C = list(chain.from_iterable(v[:len(v) - K + 1]for v in G if len(v) >= K))

    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, *A = map(int, open(0).read().split())

ans = float("inf")
for Y in set(A):
    C = []
    tmp = []
    for a in A:
        if a >= Y:
            tmp.append(a)
        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, *A = map(int, open(0).read().split())

ans = float("inf")
for Y in A:
    C = []
    tmp = []
    for a in A:
        if a >= Y:
            tmp.append(a)
        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:
inf = 10 ** 9

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

ans = inf
for min_ in sorted(set(a)):
    res = []  # 最小値min_としたとき、取り除ける要素全て
    seq = 0
    for ind, a_ in enumerate(a):
        if a_ >= min_:
            seq += 1
        else:
            if seq >= k:
                sequence_le_k = a[ind - seq:ind]  # 長さk以上の数列
                pick = seq - k + 1  # この個数だけ取り除く
                res.extend(sorted(sequence_le_k)[:pick])
            seq = 0
    else:
        if seq >= k:
            sequence_le_k = a[-seq:]  # 長さk以上の数列
            pick = seq - k + 1  # この個数だけ取り除く
            res.extend(sorted(sequence_le_k)[:pick])
    if len(res) < q:
        continue
    res.sort()
    ans = min(ans, res[q - 1] - min_)  # q回目に取り除いた要素 = 取り除く最大値
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    res = 10**9
    for e in a:
        tank = []
        new = []
        for je in a:
            if e <= je:
                tank.append(je)
            else:
                if len(tank) >= k:
                    tank.sort()
                    for i in range(len(tank)-k+1):
                        new.append(tank[i])
                tank = []
        if len(tank) >= k:
            tank.sort()
            for i in range(len(tank)-k+1):
                new.append(tank[i])
        new.sort()
        if len(new) > q-1:
            res = min(res,new[q-1]-e)
    print(res)

if __name__ =='__main__':
    main()

Submission status: Accepted

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

ans = float("inf")

# 最小値Y決め打ち
for Y in A:
    # Y以下の場所で区切る
    B = []
    tmp = []
    for a in A:
        if a < Y:
            if tmp:
                B.append(tmp)
                tmp = []
        else:
            tmp.append(a)
    if tmp:
        B.append(tmp)
        tmp = []

    cand = []
    # 操作可能な区間を各々ソート
    B = [sorted(b) for b in B]
    for b in B:
        # 各区間 len(b)-K+1個まで取り除ける
        # 小さい方から選んでいく
        r = max(len(b)-K+1, 0)
        cand += b[:r]
    # 候補をソート
    cand = sorted(cand)
    # Q個以上ならok 最大値の最小値はQ番目になる
    if len(cand) >= Q:
        X = cand[Q-1]
        ans = min(ans, X - Y)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

N0 = 2**(N-1).bit_length()
INF = 2**31-1
seg_min = [INF]*(2*N0)
seg_min_idx = [0] * (2 * N0)


def update(idx, value):
    idx += N0 - 1
    seg_min[idx] = value
    seg_min_idx[idx] = idx
    while idx > 0:
        idx = (idx - 1) // 2
        seg_min[idx] = min(seg_min[idx * 2 + 1], seg_min[idx * 2 + 2])
        seg_min_idx[idx] = seg_min_idx[idx * 2 + 1] if seg_min[idx * 2 + 1] <= seg_min[idx * 2 + 2] else seg_min_idx[idx * 2 + 2]


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret = INF
    min_idx = 0
    while first <= last:
        if not first & 1:
            if seg_min[first] < ret:
                min_idx = seg_min_idx[first]
            ret = min(ret, seg_min[first])
        if last & 1:
            if seg_min[last] < ret:
                min_idx = seg_min_idx[last]
            ret = min(ret, seg_min[last])
        first = first // 2
        last = last // 2 - 1
    min_idx -= (N0-1)
    return ret, min_idx


for i, x in enumerate(A):
    update(i, x)

A_index = []
left_right_used = []
for i, x in enumerate(A):
    A_index.append((x, i))
    left_right_used.append([i, i, 0])
A_index.sort(key=lambda a: a[0], reverse=True)

pq = []
ans = 10 ** 10
for i in range(N):
    left_used_flag = 0
    right_used_flag = 0
    index = A_index[i][1]
    left_right_used[index][2] = 1
    if index - 1 >= 0:
        if left_right_used[index - 1][2] == 1:
            left_used_flag = 1
    if index + 1 < N:
        if left_right_used[index + 1][2] == 1:
            right_used_flag = 1
    if left_used_flag == 1 and right_used_flag == 1:
        leftmost = left_right_used[index - 1][0]
        rightmost = left_right_used[index + 1][1]
    elif left_used_flag == 1 and right_used_flag == 0:
        leftmost = left_right_used[index - 1][0]
        rightmost = index
    elif left_used_flag == 0 and right_used_flag == 1:
        leftmost = index
        rightmost = left_right_used[index + 1][1]
    else:
        leftmost = rightmost = index
    num_old = max(0, left_right_used[leftmost][1] - left_right_used[leftmost][0] - K + 2) * left_used_flag\
              + max(0, left_right_used[rightmost][1] - left_right_used[rightmost][0] - K + 2) * right_used_flag
    left_right_used[leftmost][1] = rightmost
    left_right_used[rightmost][0] = leftmost
    num_new = max(0, left_right_used[leftmost][1] - left_right_used[leftmost][0] - K + 2)
    num_add = num_new - num_old
    for j in range(num_add):
        range_min, min_index = query(leftmost, rightmost)
        update(min_index, 10 ** 10)
        heapq.heappush(pq, range_min * (-1))

    for j in range(num_add):
        if len(pq) > Q:
            heapq.heappop(pq)
    if len(pq) == Q:
        maximum = heapq.heappop(pq) * (-1)
        ans_new = maximum - A[index]
        ans = min(ans, ans_new)
        heapq.heappush(pq, maximum * (-1))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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:
			que = []
		else:
			heapq.heappush(que, a[i])
			if len(que) == k:
				removed.append(heapq.heappop(que))
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q-1] - x)
print(ans)

Submission status: Accepted

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

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


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

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

print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

print(answer)

Submission status: Accepted

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

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(a) - a for a in A)

# 出力
print(ans)

Submission status: Accepted

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

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(a) - a for a in sorted(A))

# 出力
print(ans)

Submission status: Accepted

Solution code:
def main():
    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)
main()

Submission status: Accepted

Solution code:
n, k, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()] + [-1]
ans = 10**15
for min_val in a[:-1]:
    takeble = []
    l, r = -1, -1 
    for i, item in enumerate(a):
        if item >= min_val and l == -1:
            l = i
        elif item < min_val and l != -1:
            r = i
            takeble.append(a[l:r])
            l = -1
    taken = []
    for part in takeble:
        if len(part) < k:
            continue
        part.sort()
        taken += part[:len(part)-k+1]
    if len(taken) < q:
        continue
    taken.sort()
    ans = min(ans, taken[q-1] - taken[0])
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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