Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 2000

1 \leq K \leq N

1 \leq Q \leq N-K+1

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 ... A_N

Output

Print the smallest possible value of X-Y.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

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

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

451211184



Sample input:
5 3 2
4 3 1 5 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            tmp_length = 1
            for j in range(a_index-1,-1,-1):
                if j < 0:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] <= b_value:
                    continue
                tmp_length += 1
                if tmp_length >= K:
                    break
            tmp_length -= 1
            for j in range(a_index+1,N):
                if j > N-1:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] < b_value:
                    continue
                length += 1
                if length >= K:
                    break
            length += tmp_length
            if length >= K:
                count += 1
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            tmp_length = 1
            for j in range(a_index-1,-1,-1):
                if j < 0:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] <= b_value:
                    continue
                tmp_length += 1
                if tmp_length >= K:
                    break
            tmp_length -= 1
            for j in range(a_index+1,N):
                if j > N-1:
                    break 
                if A[j] < B[key]:
                    break
                if B[key] <= A[j] <= b_value:
                    continue
                length += 1
                if length >= K:
                    break
            length += tmp_length
            if length >= K:
                count += 1
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            for j in range(a_index-1,a_index-K,-1):
                if j < 0:
                    break 
                if A[j] < B[key]:
                    break
                length += 1
            for j in range(a_index+1,a_index+K):
                if j > N-1:
                    break 
                if A[j] < B[key]:
                    break
                length += 1
            if length >= K:
                count += 1
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_key in range(key,key+Q):
        b_value = B[b_key]
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        success_count = min(len(a_indeces),key + Q - b_key)
        count = 0

        for a_index in a_indeces:
            length = 1
            for j in range(a_index-1,a_index-K,-1):
                if j < 0:
                    break 
                if A[j] < b_value:
                    break
                length += 1
            for j in range(a_index+1,a_index+K):
                if j > N-1:
                    break 
                if A[j] < b_value:
                    break
                length += 1
            if length >= K:
                count += 1
                break
        if count < success_count:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = False
    for b_value in B[key:key+Q]:
        a_indeces = [i for i, x in enumerate(A) if x == b_value]
        for a_index in a_indeces:
            length = 1
            for j in range(a_index-1,a_index-K,-1):
                if j < 0:
                    break 
                if A[j] < b_value:
                    break
                length += 1
            for j in range(a_index+1,a_index+K):
                if j > N-1:
                    break 
                if A[j] < b_value:
                    break
                length += 1
            if length >= K:
                f = True
                break
        if not f:
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()
if Q == N - K + 1:
    print(L[0][1])
    exit()
if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

a = A[N-K-Q+1:K+Q-1]
# 必ず選ばないといけない要素
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        # 必ず最小値が含まれるなら
        print(L[0][1])
        exit()
    sL = [i for i in sL if i[0] <= m_index]
    # 最小値の幅が狭まるためsLを更新
for key,value in sL:
    f = True
    for b_value in B[key:key+Q]:
        a_index = A.index(b_value)
        length = 1
        for j in range(a_index-1,a_index-K,-1):
            if j < 0:
                break 
            if A[j] < b_value:
                break
            length += 1
        for j in range(a_index+1,a_index+K):
            if j > N-1:
                break 
            if A[j] < b_value:
                break
            length += 1
        if length < K:
            f = False
            break
        
    if f:
        print(value)
        exit()

print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A)
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)]
sL = sorted(L,key=lambda x:x[1])

if Q == 1:
    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:
    print(sL[0][1])
    exit()

m_index = len(A)-1
a = A[N-K-Q+1:K+Q-1]
if a:
    m_index = B.index(min(a))
    if m_index == 0:
        print(L[0][1])
        exit()
    sL2 = [i for i in sL if i[0] <= m_index]
    print(sL2[0][1])
    exit()
print(L[0][1])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = tuple(map(int,input().split()))
B = sorted(A)
L = sorted([[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)],key=lambda x:x[1])

if Q == 1:
    print(0)
    exit()
if Q == N - K + 1:
    print(B[Q-1] - B[0])
    exit()
if K == 1:
    print(L[0][1])
    exit()
print(B[Q-1] - B[0])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = tuple(map(int,input().split()))
B = sorted(A)
L = sorted([[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)],key=lambda x:x[1])

if Q == 1:
    print(0)
    exit()
if Q == N - K + 1:
    print(B[Q-1] - B[0])
    exit()
if K == 1:
    print(L[0])
    exit()
print(B[Q-1] - B[0])

Submission status: Wrong Answer

Solution code:
N,K,Q = map(int,input().split())
A = tuple(map(int,input().split()))
B = sorted(A)
L = sorted([[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)],key=lambda x:x[1])
print(A)
print(B)
print(L)

if Q == 1:
    print(0)
    exit()
if Q == N - K + 1:
    print(B[Q-1] - B[0])
    exit()
if K == 1:
    print(L[0])
    exit()
print(B[Q-1] - B[0])

Submission status: Wrong Answer

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

print(A[Q-1] - A[0])

Submission status: Wrong Answer

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

A = sorted(A)
if Q == 1:
    print(A[0])
else:
    print(A[Q-1] - A[0])

Submission status: Wrong Answer

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

A = sorted(A)
print(A[Q-1] - A[0])

Submission status: Wrong Answer

Solution code:
from heapq import nsmallest


def get_add_list(new_lists, removals):
    cache = {}

    def add_list(s, t):
        l = t - s
        if l >= k:
            new_lists.append((s, t))

            if (s, t) in cache:
                removals.extend(cache[s, t])
                return

            cache[s, t] = nsmallest(l - k + 1, aaa[s:t])
            removals.extend(cache[s, t])

    return add_list


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 = []
    add_list = get_add_list(new_lists, removals)
    for s, t in lists:
        for i, b in enumerate(aaa[s:t]):
            if a > b:
                add_list(s, s + i)
                s = s + i + 1
        add_list(s, t)
    if len(removals) < q:
        break
    removals.sort()
    ans = min(ans, removals[q - 1] - a)
    lists = new_lists

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):

    ans = sys.maxsize
    for a in A:
        P = []
        s = None
        for i in range(N):
            if A[i] >= a:
                if s is None:
                    s = i
            else:
                if s is not None:
                    P.append((s, i))
                    s = None
        if s is not None:
            P.append((s, N))
        B = []
        for s, e in P:
            if e - s - K + 1 > 0:
                t = sorted(A[s:e + 1])[:e - s - K + 1]
                B.extend(t)

        B.sort()
        if len(B) > Q - 1:
            ans_cnd = B[Q - 1] - B[0]
            ans = ans if ans < ans_cnd else ans_cnd
    return ans


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    # N = 2000
    # K = random.randint(1, N)
    # Q = random.randint(1, N - K + 1)
    # A = [random.randint(1, 1000000000) for _ in range(N)]
    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):

    ans = sys.maxsize
    for a in set(A):
        P = []
        s = None
        for i in range(N):
            if A[i] >= a:
                if s is None:
                    s = i
            else:
                if s is not None:
                    P.append((s, i))
                    s = None
        if s is not None:
            P.append((s, N))
        B = []
        C = []
        for s, e in P:
            if e - s - K + 1 > 0:
                t = sorted(A[s:e + 1])[:e - s - K + 1]
                B.extend(t)
                C.append(t)
        B.sort()
        if len(B) > Q - 1:
            ans_cnd = B[Q - 1] - B[0]
            ans = ans if ans < ans_cnd else ans_cnd
    return ans


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    # N = 2000
    # K = random.randint(1, N)
    # Q = random.randint(1, N - K + 1)
    # A = [random.randint(1, 1000000000) for _ in range(N)]
    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):
    if Q == 1:
        return 0
    ans = sys.maxsize
    for i in range(N):
        x = A[i]
        s = 0
        yc = []
        for j in range(N):
            if A[j] < x:
                for c in sorted(A[s:j])[:len(A[s:j]) - Q + 1]:
                    bisect.insort(yc, c)
                s = j + 1
        else:
            for c in sorted(A[s:])[:len(A[s:]) - Q + 1]:
                bisect.insort(yc, c)

        if yc and len(yc) > Q - 1:
            ans = ans if ans < yc[Q - 1] - x else yc[Q - 1] - x

    return ans


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    # N = 2000
    # K = random.randint(1, N)
    # Q = random.randint(1, N - K + 1)
    # A = [random.randint(1, 1000000000) for _ in range(N)]
    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):
    if Q == 1:
        return 0
    ans = sys.maxsize
    for i in range(N):
        x = A[i]
        s = 0
        yc = []
        for j in range(N):
            if A[j] < x or i == j:
                for c in sorted(A[s:j])[:len(A[s:j]) - Q + 2]:
                    bisect.insort(yc, c)
                s = j + 1
        else:
            for c in sorted(A[s:])[:len(A[s:]) - Q + 2]:
                bisect.insort(yc, c)

        if yc and len(yc) > Q - 2:
            # print(yc, yc[Q - 2], x, yc[Q - 2] - x)
            ans = ans if ans < yc[Q - 2] - x else yc[Q - 2] - x

    return ans


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    # N = 2000
    # K = random.randint(1, N)
    # Q = 1  #random.randint(1, N - K + 1)
    # A = [random.randint(1, 1000000000) for _ in range(N)]
    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def split_by_floor(arr, floor):
    ans = []
    tmp = []
    for e in arr:
        if e < floor and tmp:
            ans.append(tmp)
            tmp = []
        else:
            tmp.append(e)
    if tmp:
        ans.append(tmp)
    return ans

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

floor_cands = list(sorted(set(arr)))
ans = floor_cands[-1] - floor_cands[0]

for floor in floor_cands:
    splitted_arrs = split_by_floor(arr, floor)
    cands = []
    for splitted in splitted_arrs:
        cands.extend(sorted(splitted)[:len(splitted) - K + 1])
    if len(cands) < Q:
        continue
    sorted_cands = list(sorted(cands))
    tmp_ans = sorted_cands[Q - 1] - sorted_cands[0]
    if ans > tmp_ans:
        ans = tmp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
def split_by_floor(arr, floor):
    ans = []
    tmp = []
    for e in arr:
        if e < floor and tmp:
            ans.append(tmp)
            tmp = []
        else:
            tmp.append(e)
    if tmp:
        ans.append(tmp)
    return ans

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

floor_cands = list(sorted(set(arr)))
print(floor_cands)
ans = floor_cands[-1] - floor_cands[0]
print(ans)

for floor in floor_cands:
    splitted_arrs = split_by_floor(arr, floor)
    cands = []
    for splitted in splitted_arrs:
        cands.extend(sorted(splitted)[:len(splitted) - K + 1])
    if len(cands) < Q:
        continue
    sorted_cands = list(sorted(cands))
    tmp_ans = sorted_cands[Q - 1] - sorted_cands[0]
    if ans > tmp_ans:
        ans = tmp_ans
    print(floor, tmp_ans)

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import time
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, Q, A):
    A.sort()
    return A[Q - 1] - A[0]


def main():
    N, K, Q = read_int_n()
    A = read_int_n()

    print(slv(N, K, Q, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()
print(A[q-1] - A[0])

Submission status: Wrong Answer

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

src.sort()
b = src[Q-1]
a = src[0]
print(b-a)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = [int(x) for x in input().split()]
m = None
for x in a:
    b = []
    c = []
    for y in a:
        if y < x:
            if len(c) > k:
                c.sort()
                b.extend(c[:len(c) - k + 1])
            c = []
        else:
            c.append(y)
    if len(c) > k:
        c.sort()
        b.extend(c[:len(c) - k + 1])
    if len(b) >= q:
        b.sort()
        if m is None or m > b[q - 1] - x: m = b[q - 1] - x
print(m)

Submission status: Wrong Answer

Solution code:
n, k, q = map(int, input().split())
a = [int(x) for x in input().split()]
m = None
for x in a:
    b = []
    c = []
    for y in a:
        if y < x:
            if len(c) > k:
                c.sort()
                b.extend(c[:len(c) - k + 1])
            c = []
        else:
            c.append(y)
    if len(c) > k:
        c.sort()
        b.extend(c[:len(c) - k + 1])
    if len(b) >= q:
        b.sort()
        if m is None or m > b[q - 1]: m = b[q - 1] - x
print(m)

Submission status: Wrong Answer

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
sortedA = sorted(set(A))
ans = []
for v in sortedA:
    C = [[]]
    for i, t in enumerate(A):
        if t < v  and len(C[-1]) > 0 :
            C.append([])
        if t >= v :
            C[-1].append(t)
    tmp = []
    for t in C:
        if len(t) >= K:
            tmp += sorted(t)[:len(t)-K+1]
    if len(tmp) >= Q:
        ans.append(tmp[Q-1] - v)
print(min(ans))

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 bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            if i == n:
                ma = 99999999999
            else:
                ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c >= k and c > cc:
                        g += c - max(k-1, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t >= ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c >= k and c > cc:
                g += c - max(k-1, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n+1)
        # print(i,l,mi)
        if l > n or l <= i+1:
            continue
        t = sa[l-1] - mi
        if r > t:
            r = t


    return r




print(main())

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def n_removable(N, ix, K):
    # ix is sorted
    cnt = max(0, ix[0] - K + 1)
    for j in range(len(ix) - 1):
        cnt += max(0, ix[j+1] - ix[j] - K)
    cnt += max(0, N - ix[-1] - K)
    return cnt


def manage_luck_flag(luck_flag, j, K):
    luck_flag[j] = 1
    N = len(luck_flag)
    if j < K:
        luck_flag[:j+1] = 1
    if j >= N - K:
        luck_flag[-j-1:] = 1
    if K <= j < N - K:
        for k in range(1, K+1):
            if luck_flag[j - k] == 1:
                for p in range(k+1):
                    luck_flag[j - p] = 1
                break
        for k in range(1, K+1):
            if luck_flag[j + k] == 1:
                for p in range(k+1):
                    luck_flag[j + p] = 1
                break  
    
    return luck_flag


def main(N, K, Q, A):
    A = np.array(A)
    Asort = np.sort(A)
    ix = np.argsort(A)
    luck_ix = []

    diff = Asort[Q-1] - Asort[0]

    luck_flag = np.zeros(N)

    for i in range(N-Q-1):
        bisect.insort(luck_ix, ix[i])
        luck_flag = manage_luck_flag(luck_flag, ix[i], K)
        if A[ix[i]] == A[ix[i+1]]: continue  # 同じ要素は全部消す

        cnt = n_removable(N, luck_ix, K)
        if Q > cnt:
            return diff

        Asortd = np.sort(A[(1 - luck_flag).astype(bool)])
        # print(luck_flag, Asortd, cnt)
        if len(Asortd) < Q:
            return diff

        diff = min(diff, Asortd[Q-1] - Asortd[0])

    return diff

if __name__ == '__main__':
    N, K, Q = lii()
    A = lii()
    print(main(N, K, Q, A))
    exit()

    # for _ in range(100):
    #     N = 20000
    #     K = np.random.randint(N) + 1
    #     Q = np.random.randint(N - K + 1) + 1
    #     A = np.random.randint(20, size=N)
    #     print(N, K, Q, A)
        # print(main(N, K, Q, A))