結果

問題 No.3605 Grand Cross
コンテスト
ユーザー askr58
提出日時 2026-07-25 02:54:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 437 ms / 2,000 ms
+ 10µs
コード長 2,303 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 241 ms
コンパイル使用メモリ 95,844 KB
実行使用メモリ 256,392 KB
最終ジャッジ日時 2026-07-31 20:51:03
合計ジャッジ時間 21,139 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#generated by ChatGPT
import sys
from bisect import bisect_right


def solve_left(a, b, c, d):
    """
    a 側の部分列が a[0] を含む場合の最大スコアを求める。
    """
    n = len(a)
    m = len(b)

    # 累積和
    asum = [0] * (n + 1)
    bsum = [0] * (m + 1)

    for i in range(n):
        asum[i + 1] = asum[i] + a[i]

    for i in range(m):
        bsum[i + 1] = bsum[i] + b[i]

    # positions[color] :=
    # a において、その色が現れる位置の昇順リスト
    positions = [[] for _ in range(n + m)]

    for i in range(n):
        positions[c[i]].append(i)

    result = -1
    max_center = (n - 1) // 2

    # b 側の中心 j を固定する
    for j in range(m):
        limit = min(
            j,
            m - 1 - j,
            max_center,
        )

        pos = positions[d[j]]

        # limit 以下の最大位置を探す
        k = bisect_right(pos, limit)

        if k == 0:
            continue

        i = pos[k - 1]

        # a 側の区間は [0, 2i]
        sum_a = asum[2 * i + 1]

        # b 側の区間は [j-i, j+i]
        sum_b = bsum[j + i + 1] - bsum[j - i]

        result = max(result, sum_a + sum_b)

    return result


def main():
    input_data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(input_data)

    t = next(it)
    answers = []

    for _ in range(t):
        n = next(it)
        m = next(it)

        a = [next(it) for _ in range(n)]
        b = [next(it) for _ in range(m)]

        c = [next(it) - 1 for _ in range(n)]
        d = [next(it) - 1 for _ in range(m)]

        answer = -1

        # X が A_1 を含む場合
        answer = max(answer, solve_left(a, b, c, d))

        # X が A_N を含む場合
        a.reverse()
        c.reverse()

        answer = max(answer, solve_left(a, b, c, d))

        # 元に戻す
        a.reverse()
        c.reverse()

        # A と B を交換
        a, b = b, a
        c, d = d, c

        # Y が B_1 を含む場合
        answer = max(answer, solve_left(a, b, c, d))

        # Y が B_M を含む場合
        a.reverse()
        c.reverse()

        answer = max(answer, solve_left(a, b, c, d))

        answers.append(str(answer))

    sys.stdout.write("\n".join(answers))


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