Constraints

• 0 <= len(d) <= 200000
• 1 <= d[i] <= 1000000000 for every valid i
• 0 <= A <= 1000000000
• The answer fits in a signed 64-bit integer.

Examples

Solution

def solution(d, A):
    from bisect import bisect_left, bisect_right

    if not d:
        return 0

    values = sorted(set(d))
    m = len(values)
    bit = [0] * (m + 1)

    def update(idx, val):
        while idx <= m:
            if val > bit[idx]:
                bit[idx] = val
            idx += idx & -idx

    def query(idx):
        best = 0
        while idx > 0:
            if bit[idx] > best:
                best = bit[idx]
            idx -= idx & -idx
        return best

    ans = 0
    for x in d:
        limit = A - x
        pos = bisect_right(values, limit)
        best_before = query(pos)
        cur = best_before + x
        if cur > ans:
            ans = cur

        compressed_idx = bisect_left(values, x) + 1
        update(compressed_idx, cur)

    return ans

Time complexity: O(n log m), where n = len(d) and m is the number of distinct durations.. Space complexity: O(m), where m is the number of distinct durations..

Hints

1. Let dp[i] be the best total watched duration for a valid subsequence that ends at video i.
2. For video i with duration x, you need the maximum dp[j] among previous videos with d[j] <= A - x. Maintain prefix maximums over durations.

Constraints

• 0 <= len(d) <= 5000
• 0 <= K <= 5000
• 1 <= d[i] <= 1000000000 for every valid i
• 0 <= A <= 1000000000
• Let m = len(set(d)). Test data satisfies m * max(1, K) <= 5000000.

Examples

Solution

def solution(d, A, K):
    from bisect import bisect_right

    if K <= 0 or not d:
        return 0

    values = sorted(set(d))
    m = len(values)

    # prev[i] is the best total for the current length ending with values[i].
    prev = list(values)  # Length 1 sequences.
    ans = max(prev)

    if K == 1:
        return ans

    NEG = -10**30

    def bit_update(bit, idx, val):
        while idx <= m:
            if val > bit[idx]:
                bit[idx] = val
            idx += idx & -idx

    def bit_query(bit, idx):
        best = NEG
        while idx > 0:
            if bit[idx] > best:
                best = bit[idx]
            idx -= idx & -idx
        return best

    for _ in range(2, K + 1):
        bit = [NEG] * (m + 1)
        for i, total in enumerate(prev, 1):
            if total != NEG:
                bit_update(bit, i, total)

        cur = [NEG] * m
        any_state = False

        for i, x in enumerate(values):
            pos = bisect_right(values, A - x)
            if pos == 0:
                continue

            best_before = bit_query(bit, pos)
            if best_before == NEG:
                continue

            total = best_before + x
            cur[i] = total
            if total > ans:
                ans = total
            any_state = True

        if not any_state:
            break

        prev = cur

    return ans

Time complexity: O(K * m log m), where m is the number of distinct durations.. Space complexity: O(m), where m is the number of distinct durations..

Hints

1. Because replays are allowed, the original indices no longer matter. The useful state is the last watched duration and how many videos have been watched.
2. For each sequence length and next duration x, transition from the best previous state whose last duration is at most A - x. This can be accelerated with sorted durations and prefix maximums.