結果
問題 | No.1324 Approximate the Matrix |
ユーザー | shotoyoo |
提出日時 | 2020-12-22 00:23:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 6,232 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 81,808 KB |
実行使用メモリ | 89,088 KB |
最終ジャッジ日時 | 2023-10-21 12:12:27 |
合計ジャッジ時間 | 8,307 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
70,280 KB |
testcase_01 | AC | 62 ms
70,280 KB |
testcase_02 | AC | 62 ms
70,280 KB |
testcase_03 | AC | 232 ms
84,060 KB |
testcase_04 | AC | 236 ms
84,232 KB |
testcase_05 | AC | 232 ms
84,468 KB |
testcase_06 | AC | 228 ms
83,976 KB |
testcase_07 | AC | 284 ms
84,364 KB |
testcase_08 | AC | 116 ms
79,112 KB |
testcase_09 | AC | 146 ms
79,744 KB |
testcase_10 | AC | 167 ms
80,808 KB |
testcase_11 | AC | 168 ms
81,104 KB |
testcase_12 | AC | 143 ms
79,868 KB |
testcase_13 | AC | 119 ms
79,064 KB |
testcase_14 | AC | 167 ms
80,904 KB |
testcase_15 | AC | 143 ms
79,892 KB |
testcase_16 | AC | 112 ms
78,360 KB |
testcase_17 | AC | 193 ms
81,184 KB |
testcase_18 | AC | 129 ms
79,752 KB |
testcase_19 | AC | 157 ms
79,696 KB |
testcase_20 | AC | 114 ms
79,064 KB |
testcase_21 | AC | 113 ms
78,944 KB |
testcase_22 | AC | 88 ms
78,288 KB |
testcase_23 | AC | 166 ms
80,404 KB |
testcase_24 | AC | 185 ms
81,576 KB |
testcase_25 | AC | 174 ms
80,824 KB |
testcase_26 | AC | 179 ms
80,784 KB |
testcase_27 | AC | 168 ms
80,604 KB |
testcase_28 | AC | 64 ms
70,316 KB |
testcase_29 | AC | 82 ms
77,872 KB |
testcase_30 | AC | 85 ms
77,744 KB |
testcase_31 | AC | 94 ms
78,196 KB |
testcase_32 | AC | 60 ms
70,316 KB |
testcase_33 | AC | 66 ms
70,316 KB |
testcase_34 | AC | 60 ms
70,316 KB |
testcase_35 | AC | 62 ms
70,316 KB |
testcase_36 | AC | 62 ms
70,316 KB |
testcase_37 | AC | 338 ms
88,920 KB |
testcase_38 | AC | 275 ms
89,088 KB |
testcase_39 | AC | 277 ms
88,440 KB |
testcase_40 | AC | 276 ms
88,912 KB |
testcase_41 | AC | 275 ms
88,792 KB |
testcase_42 | AC | 85 ms
78,252 KB |
testcase_43 | AC | 84 ms
78,236 KB |
testcase_44 | AC | 85 ms
78,256 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") from typing import NamedTuple, Optional, List, Tuple, cast from heapq import heappush, heappop class MCFGraph: class Edge(NamedTuple): src: int dst: int cap: int flow: int cost: int class _Edge: def __init__(self, dst: int, cap: int, cost: int) -> None: self.dst = dst self.cap = cap self.cost = cost self.rev: Optional[MCFGraph._Edge] = None def __init__(self, n: int, neg=False, negf=None) -> None: self._neg = neg if neg: n += 2 self._negs = n-2 self._negt = n-1 self._negf = negf self._negfsum = 0 self._negcsum = 0 self._negdone = False self._n = n self._g: List[List[MCFGraph._Edge]] = [[] for _ in range(n)] self._edges: List[MCFGraph._Edge] = [] def add_edge(self, src: int, dst: int, cap: int, cost: int) -> int: assert 0 <= src < self._n assert 0 <= dst < self._n assert 0 <= cap if cost<0 and self._neg: if not self._negdone: global s,t self._negdone = True self.add_edge(self._negs, s, self._negf, 0) self.add_edge(t, self._negt, self._negf, 0) # 後で指定した流量を流すための処理 # self._inf = 10**12 # self._negE = self.add_edge(self._negt, self._negs, self._negf, -self._inf) self.add_edge(self._negs, dst, cap, 0) self.add_edge(src, self._negt, cap, 0) self.add_edge(dst, src, cap, -cost) self._negfsum += cap self._negcsum += cap*cost else: m = len(self._edges) e = MCFGraph._Edge(dst, cap, cost) re = MCFGraph._Edge(src, 0, -cost) e.rev = re re.rev = e self._g[src].append(e) self._g[dst].append(re) self._edges.append(e) return m def get_edge(self, i: int) -> Edge: assert 0 <= i < len(self._edges) e = self._edges[i] re = cast(MCFGraph._Edge, e.rev) return MCFGraph.Edge( re.dst, e.dst, e.cap + re.cap, re.cap, e.cost ) def edges(self) -> List[Edge]: return [self.get_edge(i) for i in range(len(self._edges))] def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> Tuple[int, int]: if self._neg: flow_limit += self._negfsum val = self.slope(self._negs, self._negt, flow_limit)[-1] return (val[0], val[1] + self._negcsum) else: return self.slope(s, t, flow_limit)[-1] def slope(self, s: int, t: int, flow_limit: Optional[int] = None) -> List[Tuple[int, int]]: assert 0 <= s < self._n assert 0 <= t < self._n assert s != t if flow_limit is None: flow_limit = cast(int, sum(e.cap for e in self._g[s])) dual = [0] * self._n prev: List[Optional[Tuple[int, MCFGraph._Edge]]] = [None] * self._n def refine_dual() -> bool: pq = [self.enc(0, s)] visited = [False] * self._n dist: List[Optional[int]] = [None] * self._n dist[s] = 0 while pq: dist_v, v = self.dec(heappop(pq)) if visited[v]: continue visited[v] = True if v == t: break dual_v = dual[v] for e in self._g[v]: w = e.dst if visited[w] or e.cap == 0: continue reduced_cost = e.cost - dual[w] + dual_v new_dist = dist_v + reduced_cost dist_w = dist[w] if dist_w is None or new_dist < dist_w: dist[w] = new_dist prev[w] = v, e heappush(pq, self.enc(new_dist, w)) else: return False dist_t = dist[t] for v in range(self._n): if visited[v]: dual[v] -= cast(int, dist_t) - cast(int, dist[v]) return True flow = 0 cost = 0 prev_cost_per_flow: Optional[int] = None result = [(flow, cost)] while flow < flow_limit: if not refine_dual(): break f = flow_limit - flow v = t while prev[v] is not None: u, e = cast(Tuple[int, MCFGraph._Edge], prev[v]) f = min(f, e.cap) v = u v = t while prev[v] is not None: u, e = cast(Tuple[int, MCFGraph._Edge], prev[v]) e.cap -= f assert e.rev is not None e.rev.cap += f v = u c = -dual[s] flow += f cost += f * c if c == prev_cost_per_flow: result.pop() result.append((flow, cost)) prev_cost_per_flow = c return result def enc(self,d,v): return d*(self._n)+v def dec(self,val): return divmod(val,self._n) n,k = list(map(int, input().split())) a = list(map(int, input().split())) b = list(map(int, input().split())) p = [list(map(int, input().split())) for _ in range(n)] num = 2*n + 2 # g = MCFGraph(num, neg=True, negf=k) g = MCFGraph(num) s = num-2 t = num-1 for i in range(n): for j in range(n): for ind in range(min(a[i],b[j])): cost = -2*p[i][j] + 1 + 2*ind g.add_edge(i,n+j,1,cost) # print(i,j,cost) # g.add_edge(pij(i,j), t, a[i]+b[j], cost) # cost<0のときは? for i in range(n): g.add_edge(s, i, a[i], 0) for j in range(n): g.add_edge(n+j, t, b[j], 0) val = g.flow(s,t,k) ans = sum(p[i][j]**2 for i in range(n) for j in range(n)) + val[1] print(ans)