結果

問題 No.2006 Decrease All to Zero
ユーザー lam6er
提出日時 2025-03-31 17:58:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,677 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 69,264 KB
最終ジャッジ日時 2025-03-31 17:59:44
合計ジャッジ時間 6,708 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 5 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    X = list(map(int, input[idx:idx+n]))
    idx += n
    A = list(map(int, input[idx:idx+n]))
    idx += n

    total = sum(A)
    max_a = max(A)
    sum_others = total - max_a

    if max_a > sum_others + 1:
        print(-1)
        return

    # Precompute the sorted list of other buttons for each i, ordered by distance and then X
    pre_sorted = [[] for _ in range(n)]
    for i in range(n):
        others = []
        for j in range(n):
            if j != i:
                others.append((j, abs(X[j] - X[i])))
        # Sort by distance, then by X[j] (smaller X first if distances are equal)
        others.sort(key=lambda x: (x[1], X[x[0]]))
        pre_sorted[i] = [j for j, _ in others]

    min_total = float('inf')

    # Iterate each possible starting button
    for start in range(n):
        if A[start] == 0:
            continue
        restA = A.copy()
        current = start
        restA[current] -= 1
        total_d = 0
        valid = True

        for _ in range(total - 1):
            found = False
            for j in pre_sorted[current]:
                if restA[j] > 0:
                    total_d += abs(X[j] - X[current])
                    restA[j] -= 1
                    current = j
                    found = True
                    break
            if not found:
                valid = False
                break
        if valid and total_d < min_total:
            min_total = total_d

    if min_total == float('inf'):
        print(-1)
    else:
        print(min_total)

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