結果

問題 No.2434 RAKUTAN de RAKUTAN
ユーザー lam6er
提出日時 2025-03-26 15:58:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,799 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 78,560 KB
最終ジャッジ日時 2025-03-26 15:59:43
合計ジャッジ時間 2,897 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    H = int(input[idx]); idx += 1
    X = int(input[idx]); idx += 1

    G = int(input[idx]); idx +=1
    g_list = list(map(int, input[idx:idx+G]))
    idx += G
    B = int(input[idx]); idx +=1
    b_list = list(map(int, input[idx:idx+B]))
    idx += B

    g_list.sort()
    b_list.sort()

    intervals = set()

    all_pos = set(g_list + b_list)

    for p in all_pos:
        min_a = max(0, p - (X - 1))
        max_a = min(p - 1, N - X)
        if min_a > max_a:
            continue
        for a in range(min_a, max_a + 1):
            start = a + 1
            end = a + X - 1
            intervals.add((start, end))

    interval_scores = []
    for (start, end) in intervals:
        g_left = bisect.bisect_left(g_list, start)
        g_right = bisect.bisect_right(g_list, end)
        g_count = g_right - g_left

        b_left = bisect.bisect_left(b_list, start)
        b_right = bisect.bisect_right(b_list, end)
        b_count = b_right - b_left

        score = b_count - g_count
        if score > 0:
            interval_scores.append((-score, start, end))

    interval_scores.sort()
    sorted_intervals = []
    for sc, s, e in interval_scores:
        sorted_intervals.append((s, e, -sc))

    selected = []
    last_end = -1
    for s, e, sc in sorted_intervals:
        if s > last_end:
            selected.append(sc)
            last_end = e

    prefix = [0] * (len(selected) + 1)
    for i in range(len(selected)):
        prefix[i + 1] = prefix[i] + selected[i]

    max_k = min(H, len(selected))
    max_score = prefix[max_k]

    base = len(g_list) - len(b_list)
    ans = base + max_score
    print(ans)

if __name__ == "__main__":
    main()
0