結果
問題 | No.2573 moving up |
ユーザー |
👑 |
提出日時 | 2023-12-10 18:11:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 1,626 bytes |
コンパイル時間 | 229 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 76,544 KB |
最終ジャッジ日時 | 2024-09-27 04:08:35 |
合計ジャッジ時間 | 3,821 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
def Hungarian(A, inf=1 << 60):n = len(A) + 1m = len(A[0]) + 1P = [0] * mway = [0] * mU = [0] * nV = [0] * mfor i in range(1, n):P[0] = iminV = [inf] * mused = [False] * mj0 = 0while P[j0] != 0:i0 = P[j0]j1 = 0used[j0] = Truedelta = inffor j in range(1, m):if used[j]:continueif i0 == 0 or j == 0:cur = -U[i0] - V[j]else:cur = A[i0 - 1][j - 1] - U[i0] - V[j]if cur < minV[j]:minV[j] = curway[j] = j0if minV[j] < delta:delta = minV[j]j1 = jfor j in range(m):if used[j]:U[P[j]] += deltaV[j] -= deltaelse:minV[j] -= deltaj0 = j1P[j0] = P[way[j0]]while j0 != 0:j1 = way[j0]P[j0] = P[j1]j0 = j1ret = [-1] * (n - 1)for j in range(1, m):if P[j] != 0:ret[P[j] - 1] = j - 1return -V[0], reth, w = map(int, input().split())ans = 0A = [[0] * w for _ in range(w)]for i in range(w):x, y = map(int, input().split())x -= 1y -= 1ans += xl = y - xr = yfor j in range(w):if j < l:A[i][j] = l - jelif j > r:A[i][j] = j - rres = Hungarian(A)print(res[0] + ans)