結果
問題 | No.1324 Approximate the Matrix |
ユーザー |
![]() |
提出日時 | 2020-12-21 10:47:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,292 ms / 2,000 ms |
コード長 | 2,942 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 88,928 KB |
最終ジャッジ日時 | 2024-09-21 12:44:48 |
合計ジャッジ時間 | 15,423 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
mod = 1000000007eps = 10**-9def main():import sysinput = sys.stdin.buffer.readlinefrom heapq import heappush, heappopclass Mincostflow():def __init__(self, N):self.N = Nself.adj = [[] for _ in range(N + 1)]self.inf = 1 << 60def add_edge(self, fr, to, cap, cost):# [to, cap, cost, rev]if cap == 0:returnforward = [to, cap, cost, None]backward = forward[3] = [fr, 0, -cost, forward]self.adj[fr].append(forward)self.adj[to].append(backward)def flow(self, s, t, f):N = self.Nadj = self.adjinf = self.infres = 0H = [0] * (N + 1)prev_v = [0] * (N + 1)prev_e = [None] * (N + 1)dist0 = [inf] * (N + 1)dist = [inf] * (N + 1)while f:dist[:] = dist0dist[s] = 0pq = [(0, s)]while pq:d, v = heappop(pq)if d > dist[v]:continuer0 = dist[v] + H[v]for e in adj[v]:u, cap, cost, _ = eif cap > 0 and r0 + cost - H[u] < dist[u]:dist[u] = r = r0 + cost - H[u]heappush(pq, (r, u))prev_v[u] = vprev_e[u] = e# flow f doesn't existif dist[t] == inf:return Nonefor i in range(1, N + 1):H[i] += dist[i]g = fv = twhile v != s:g = min(g, prev_e[v][1])v = prev_v[v]f -= gres += g * H[t]v = twhile v != s:e = prev_e[v]e[1] -= ge[-1][1] += gv = prev_v[v]return resN, K = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))P = []for _ in range(N):P.append(list(map(int, input().split())))s = N*2 + 1t = s + 1mcf = Mincostflow(t)for i, a in enumerate(A):va = i+1mcf.add_edge(s, va, a, 0)for j, b in enumerate(B):vb = N+j+1p = P[i][j]for f in range(min(a, b)):mcf.add_edge(va, vb, 1, 40000 - (p-f)**2 + (p-f-1)**2)for j, b in enumerate(B):vb = N+j+1mcf.add_edge(vb, t, b, 0)ans = mcf.flow(s, t, K) - 40000 * Kfor i in range(N):for j in range(N):ans += P[i][j] ** 2print(ans)if __name__ == '__main__':main()