Submission #1106144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106144		MrTEK	Swimming competition (LMIO18_plaukimo_varzybos)	Cpython 3	0 / 100	16 ms	2896 KiB

plaukimo_varzybos

def find_min_max_diff(N, A, B, AR):
    AR.sort()
    low = 0
    high = AR[-1] - AR[0]

    def is_possible(D):
        dp = [False] * (N + 1)
        dp[0] = True
        prefix_dp = [0] * (N + 1)
        prefix_dp[0] = dp[0]
        l = 0  # left pointer for the window
        for i in range(1, N + 1):
            while l < i and AR[i - 1] - AR[l] > D:
                l += 1
            min_k = max(l, i - B)
            max_k = i - A
            if min_k <= max_k:
                total_dp = prefix_dp[max_k] - (prefix_dp[min_k - 1] if min_k > 0 else 0)
                dp[i] = total_dp > 0
            else:
                dp[i] = False
            prefix_dp[i] = prefix_dp[i - 1] + dp[i]
        return dp[N]

    result = -1
    while low <= high:
        mid = (low + high) // 2
        if is_possible(mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1
    return result

# Read input
N, A, B = map(int, input().split())
AR = list(map(int, input().split()))

# Find and print the minimal possible maximum difference
print(find_min_max_diff(N, A, B, AR))

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40