結果

問題 No.1818 6 Operations
ユーザー lam6er
提出日時 2025-04-09 20:57:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,961 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,812 KB
実行使用メモリ 85,148 KB
最終ジャッジ日時 2025-04-09 20:58:51
合計ジャッジ時間 4,491 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 3 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    B = list(map(int, data[2+N:2+N+M]))
    
    # Precompute prefix sums for A and B
    prefix_a = [0] * (N + 1)
    for i in range(N):
        prefix_a[i + 1] = prefix_a[i] + A[i]
    prefix_b = [0] * (M + 1)
    for i in range(M):
        prefix_b[i + 1] = prefix_b[i] + B[i]
    
    INF = float('inf')
    dp = [[INF] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for i in range(N + 1):
        for j in range(M + 1):
            if dp[i][j] == INF:
                continue
            # Try all possible group sizes starting at i and j
            # Optimize by considering group up to remaining elements
            for k in range(1, N - i + 1):
                a_sum = prefix_a[i + k] - prefix_a[i]
                for m in range(1, M - j + 1):
                    b_sum = prefix_b[j + m] - prefix_b[j]
                    # Calculate the steps for this group pair
                    delta = b_sum - a_sum
                    merge_cost = k - 1
                    split_cost = m - 1
                    if delta >= 0:
                        max_cover = merge_cost + split_cost
                        if delta <= max_cover:
                            steps = merge_cost + split_cost + (delta)  # x+y=delta, contributes delta steps?
                            # No, no: the adjust steps are 0 in that case, but steps from group is (merge_cost + split_cost) + delta - (x+y)
                            # For minimal steps when delta <= max_cover, delta can be achieved with x + y = delta.
                            # So steps_group is (merge_cost + split_cost) + 0.
                            # Then, the adjustment steps are delta = (b - a) = (b_sum - y) - (a_sum + x) = (b_sum - a_sum) - (x + y)
                            # x + y can be delta. So that (b -a) - (x + y) =0. So no additional steps.
                            # Thus, steps_group = (merge_cost + split_cost) + 0.
                            # And additional steps are max(0, delta - max_cover) → when delta > max_cover, steps_group = (merge_cost + split_cost) + (delta - max_cover).
                            if delta <= max_cover:
                                steps = merge_cost + split_cost + 0
                            else:
                                steps = merge_cost + split_cost + (delta - max_cover)
                        else:
                            steps = merge_cost + split_cost + (delta - max_cover)
                    else:
                        steps = merge_cost + split_cost + (a_sum - b_sum)
                    if i + k <= N and j + m <= M:
                        if dp[i + k][j + m] > dp[i][j] + steps:
                            dp[i + k][j + m] = dp[i][j] + steps
    
    print(dp[N][M] if dp[N][M] != INF else -1)

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