結果
| 問題 |
No.3306 Life is Easy?
|
| コンテスト | |
| ユーザー |
 lif4635
|
| 提出日時 | 2025-10-05 16:13:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,492 bytes |
| コンパイル時間 | 273 ms |
| コンパイル使用メモリ | 82,484 KB |
| 実行使用メモリ | 106,428 KB |
| 最終ジャッジ日時 | 2025-10-05 16:13:28 |
| 合計ジャッジ時間 | 10,115 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 TLE * 2 -- * 29 |
ソースコード
# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]
mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")
prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right
import heapq
class mcf_graph:
n = 1
pos = []
g = [[]]
def __init__(self, N):
self.n = N
self.pos = []
self.g = [[] for i in range(N)]
def add_edge(self, From, To, cap, cost):
assert 0 <= From and From < self.n
assert 0 <= To and To < self.n
m = len(self.pos)
self.pos.append((From, len(self.g[From])))
self.g[From].append(
{"to": To, "rev": len(self.g[To]), "cap": cap, "cost": cost}
)
self.g[To].append(
{"to": From, "rev": len(self.g[From]) - 1, "cap": 0, "cost": -cost}
)
def get_edge(self, i):
m = len(self.pos)
assert 0 <= i and i < m
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e["to"]][_e["rev"]]
return {
"from": self.pos[i][0],
"to": _e["to"],
"cap": _e["cap"] + _re["cap"],
"flow": _re["cap"],
"cost": _e["cost"],
}
def edges(self):
m = len(self.pos)
result = [{} for i in range(m)]
for i in range(m):
tmp = self.get_edge(i)
result[i]["from"] = tmp["from"]
result[i]["to"] = tmp["to"]
result[i]["cap"] = tmp["cap"]
result[i]["flow"] = tmp["flow"]
result[i]["cost"] = tmp["cost"]
return result
def flow(self, s, t, flow_limit=-1 - (-1 << 63)):
return self.slope(s, t, flow_limit)[-1]
def slope(self, s, t, flow_limit=-1 - (-1 << 63)):
assert 0 <= s and s < self.n
assert 0 <= t and t < self.n
assert s != t
"""
variants (C = maxcost):
-(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge
"""
dual = [0 for i in range(self.n)]
dist = [0 for i in range(self.n)]
pv = [0 for i in range(self.n)]
pe = [0 for i in range(self.n)]
vis = [False for i in range(self.n)]
def dual_ref():
for i in range(self.n):
dist[i] = -1 - (-1 << 63)
pv[i] = -1
pe[i] = -1
vis[i] = False
que = []
heapq.heappush(que, (0, s))
dist[s] = 0
while que:
v = heapq.heappop(que)[1]
if vis[v]:
continue
vis[v] = True
if v == t:
break
"""
dist[v] = shortest(s, v) + dual[s] - dual[v]
dist[v] >= 0 (all reduced cost are positive)
dist[v] <= (n-1)C
"""
for i in range(len(self.g[v])):
e = self.g[v][i]
if vis[e["to"]] or (not (e["cap"])):
continue
"""
|-dual[e.to]+dual[v]| <= (n-1)C
cost <= C - -(n-1)C + 0 = nC
"""
cost = e["cost"] - dual[e["to"]] + dual[v]
if dist[e["to"]] - dist[v] > cost:
dist[e["to"]] = dist[v] + cost
pv[e["to"]] = v
pe[e["to"]] = i
heapq.heappush(que, (dist[e["to"]], e["to"]))
if not (vis[t]):
return False
for v in range(self.n):
if not (vis[v]):
continue
dual[v] -= dist[t] - dist[v]
return True
flow = 0
cost = 0
prev_cost = -1
result = [(flow, cost)]
while flow < flow_limit:
if not (dual_ref()):
break
c = flow_limit - flow
v = t
while v != s:
c = min(c, self.g[pv[v]][pe[v]]["cap"])
v = pv[v]
v = t
while v != s:
self.g[pv[v]][pe[v]]["cap"] -= c
self.g[v][self.g[pv[v]][pe[v]]["rev"]]["cap"] += c
v = pv[v]
d = -dual[s]
flow += c
cost += c * d
if prev_cost == d:
result.pop()
result.append((flow, cost))
prev_cost = cost
return result
n, m = MI()
a = LLI(n)
# 適当なマッチングにおいて
# 差を最大化したい
g = mcf_graph(2 + n + n * m + m + 10)
s = (m + 1) * n + 1
t = s + 1
off = t + 1
h = n // 2
for i in range(h): # 前半
d = (m + 1) * i # 日付用
g.add_edge(s, d, 1, 0)
for j in range(m):
p = i * (m + 1) + j + 1 # ノード
g.add_edge(d, p, 1, a[i][j])
g.add_edge(p, off + j, 1, 0)
inf = 10 ** 9
for i in range(n - h, n):
d = (m + 1) * i # 日付用
g.add_edge(d, t, 1, 0)
for j in range(m):
p = i * (m + 1) + j + 1 # ノード
g.add_edge(p, d, 1, inf - a[i][j])
g.add_edge(off + j, p, 1, 0)
f, r = g.flow(s, t)
print(inf * h - r)