結果

問題 No.3605 Grand Cross
コンテスト
ユーザー LyricalMaestro
提出日時 2026-08-01 02:34:22
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,688 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,508 ms
コンパイル使用メモリ 95,724 KB
実行使用メモリ 183,900 KB
最終ジャッジ日時 2026-08-01 02:35:04
合計ジャッジ時間 37,880 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 WA * 22 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://yukicoder.me/problems/no/3605


def fn(fn_a, fn_b, color_map, x):
    answer = -float("inf")
    for array_a, array_b in color_map.values():

        max_a = -float("inf")
        for i in array_a:
            max_a = max(max_a, fn_a(i, x))

        max_b = -float("inf")
        for i in array_b:
            max_b = max(max_b, fn_b(i, x))

        ans = max_a + max_b
        answer = max(answer, ans)
    return answer


def solve(N, M, A, B, C, D):
    cum_a_list = [0] * N
    a = 0
    for i in range(N):
        a += A[i]
        cum_a_list[i] = a
    cum_b_list = [0] * M
    b = 0
    for i in range(M):
        b += B[i]
        cum_b_list[i] = b

    color_map = {}
    for i in range(N):
        c = C[i]
        if c not in color_map:
            color_map[c] = [[], []]
        color_map[c][0].append(i)
    for i in range(M):
        c = D[i]
        if c not in color_map:
            color_map[c] = [[], []]
        color_map[c][1].append(i)

    is_ok = False
    for v_pair in color_map.values():
        if len(v_pair[0]) > 0 and len(v_pair[1]) > 0:
            is_ok = True
    if not is_ok:
        return -1

    def fn_a(i, length):
        if 0 <= i - length and i + length < N:
            if i - length == 0:
                return cum_a_list[i + length]
            else:
                return cum_a_list[i + length] - cum_a_list[i - length - 1]
        else:
            x = max(i + length - (N - 1), length - i)
            return (-10 ** 10) * x
    def fn_b(i, length):
        if 0 <= i - length and i + length < M:
            if i - length == 0:
                return cum_b_list[i + length]
            else:
                return cum_b_list[i + length] - cum_b_list[i - length - 1]
        else:
            x = max(i + length - (M - 1), length - i)
            return (-10 ** 10) * x

    low = 0
    high = N // 2
    while high - low > 2:
        v1 = (low * 2 + high) // 3
        v2 = (low + 2 * high) // 3

        if fn(fn_a, fn_b, color_map, v1) <= fn(fn_a, fn_b, color_map, v2):
            low = v1
        else:
            high = v2

    max_y = -float("inf")
    for x in range(low, high + 1):
        y = fn(fn_a, fn_b, color_map, x)
        max_y = max(y, max_y)
    return max_y

def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, M = map(int, input().split())
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        C = list(map(int, input().split()))
        D = list(map(int, input().split()))
        ans = solve(N, M, A, B, C, D)
        answers.append(ans)

    for ans in answers:
        print(ans)






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