結果
問題 |
No.3306 Life is Easy?
|
ユーザー |
|
提出日時 | 2025-10-09 16:15:41 |
言語 | Nim (2.2.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 17,922 bytes |
コンパイル時間 | 6,136 ms |
コンパイル使用メモリ | 97,540 KB |
実行使用メモリ | 65,784 KB |
最終ジャッジ日時 | 2025-10-09 16:16:04 |
合計ジャッジ時間 | 23,318 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 TLE * 3 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2]) # source: https://github.com/kemuniku/cplib/tree/main/src/cplib/tmpl/citrus.nim ImportExpand "cplib/tmpl/citrus" <=== "when not declared CPLIB_TMPL_CITRUS:\n const CPLIB_TMPL_CITRUS* = 1\n {.warning[UnusedImport]: off.}\n {.hint[XDeclaredButNotUsed]: off.}\n import os\n import algorithm\n import sequtils\n import tables\n import macros\n import std/math\n import sets\n import strutils\n import strformat\n import sugar\n import streams\n import deques\n import bitops\n import heapqueue\n import options\n import hashes\n const MODINT998244353* = 998244353\n const MODINT1000000007* = 1000000007\n when not declared CPLIB_UTILS_CONSTANTS:\n const CPLIB_UTILS_CONSTANTS* = 1\n const INF32*: int32 = 100100111.int32\n const INF64*: int = int(3300300300300300491)\n \n const INFL = INF64\n type double* = float64\n let readNext = iterator(getsChar: bool = false): string {.closure.} =\n while true:\n var si: string\n try: si = stdin.readLine\n except EOFError: yield \"\"\n for s in si.split:\n if getsChar:\n for i in 0..<s.len():\n yield s[i..i]\n else:\n if s.isEmptyOrWhitespace: continue\n yield s\n proc input*(t: typedesc[string]): string = readNext()\n proc input*(t: typedesc[char]): char = readNext(true)[0]\n proc input*(t: typedesc[int]): int = readNext().parseInt\n proc input*(t: typedesc[float]): float = readNext().parseFloat\n macro input*(t: typedesc, n: varargs[int]): untyped =\n var repStr = \"\"\n for arg in n:\n repStr &= &\"({arg.repr}).newSeqWith \"\n parseExpr(&\"{repStr}input({t})\")\n macro input*(ts: varargs[auto]): untyped =\n var tupStr = \"\"\n for t in ts:\n tupStr &= &\"input({t.repr}),\"\n parseExpr(&\"({tupStr})\")\n macro input*(n: int, ts: varargs[auto]): untyped =\n for typ in ts:\n if typ.typeKind != ntyAnything:\n error(\"Expected typedesc, got \" & typ.repr, typ)\n parseExpr(&\"({n.repr}).newSeqWith input({ts.repr})\")\n proc `fmtprint`*(x: int or string or char or bool): string = return $x\n proc `fmtprint`*(x: float or float32 or float64): string = return &\"{x:.16f}\"\n proc `fmtprint`*[T](x: seq[T] or Deque[T] or HashSet[T] or set[T]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T, N](x: array[T, N]): string = return x.toSeq.join(\" \")\n proc `fmtprint`*[T](x: HeapQueue[T]): string =\n var q = x\n while q.len != 0:\n result &= &\"{q.pop()}\"\n if q.len != 0: result &= \" \"\n proc `fmtprint`*[T](x: CountTable[T]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc `fmtprint`*[K, V](x: Table[K, V]): string =\n result = x.pairs.toSeq.mapIt(&\"{it[0]}: {it[1]}\").join(\" \")\n proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `fmtprint`]) =\n for i in 0..<len(args):\n prop.f.write(&\"{args[i]}\")\n if i != len(args) - 1: prop.f.write(prop.sepc) else: prop.f.write(prop.endc)\n if prop.flush: prop.f.flushFile()\n proc print*(args: varargs[string, `fmtprint`]) = print((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n const LOCAL_DEBUG{.booldefine.} = false\n macro getSymbolName(x: typed): string = x.toStrLit\n macro debug*(args: varargs[untyped]): untyped =\n when LOCAL_DEBUG:\n result = newNimNode(nnkStmtList, args)\n template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n for i, arg in args:\n if arg.kind == nnkStrLit:\n result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n else:\n result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n result.add(quote do: print(prop(), `arg`))\n if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n else: result.add(quote do: print(prop(), \"\\n\"))\n else:\n return (quote do: discard)\n proc `%`*(x: SomeInteger, y: SomeInteger): int =\n result = x mod y\n if y > 0 and result < 0: result += y\n if y < 0 and result > 0: result += y\n proc `//`*(x: SomeInteger, y: SomeInteger): int =\n result = x div y\n if y > 0 and result * y > x: result -= 1\n if y < 0 and result * y < x: result -= 1\n proc `^`*(x: SomeInteger, y: SomeInteger): int = x xor y\n proc `&`*(x: SomeInteger, y: SomeInteger): int = x and y\n proc `|`*(x: SomeInteger, y: SomeInteger): int = x or y\n proc `>>`*(x: SomeInteger, y: SomeInteger): int = x shr y\n proc `<<`*(x: SomeInteger, y: SomeInteger): int = x shl y\n proc `%=`*(x: var SomeInteger, y: SomeInteger): void = x = x % y\n proc `//=`*(x: var SomeInteger, y: SomeInteger): void = x = x // y\n proc `^=`*(x: var SomeInteger, y: SomeInteger): void = x = x ^ y\n proc `&=`*(x: var SomeInteger, y: SomeInteger): void = x = x & y\n proc `|=`*(x: var SomeInteger, y: SomeInteger): void = x = x | y\n proc `>>=`*(x: var SomeInteger, y: SomeInteger): void = x = x >> y\n proc `<<=`*(x: var SomeInteger, y: SomeInteger): void = x = x << y\n proc `[]`*(x, n: int): bool = (x and (1 shl n)) != 0\n proc `[]=`*(x: var int, n: int, i: bool) =\n if i: x = x or (1 << n)\n else: (if x[n]: x = x xor (1 << n))\n proc pow*(a, n: int, m = INF64): int =\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n % 2 != 0: rev = (rev * a) mod m\n if n > 1: a = (a * a) mod m\n n >>= 1\n return rev\n when not declared CPLIB_MATH_ISQRT:\n const CPLIB_MATH_ISQRT* = 1\n proc isqrt*(n: int): int =\n var x = n\n var y = (x + 1) shr 1\n while y < x:\n x = y\n y = (x + n div x) shr 1\n return x\n \n proc chmax*[T](x: var T, y: T): bool {.discardable.} = (if x < y: (x = y; return true; ) return false)\n proc chmin*[T](x: var T, y: T): bool {.discardable.} = (if x > y: (x = y; return true; ) return false)\n proc `max=`*[T](x: var T, y: T) = x = max(x, y)\n proc `min=`*[T](x: var T, y: T) = x = min(x, y)\n proc at*(x: char, a = '0'): int = int(x) - int(a)\n proc Yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n proc No*(b: bool = true): void = Yes(not b)\n proc YES_upper*(b: bool = true): void = print(if b: \"YES\" else: \"NO\")\n proc NO_upper*(b: bool = true): void = Yes_upper(not b)\n const DXY* = [(0, -1), (0, 1), (-1, 0), (1, 0)]\n const DDXY* = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]\n macro exit*(statement: untyped): untyped = (quote do: (`statement`; quit()))\n proc initHashSet[T](): Hashset[T] = initHashSet[T](0)\n" # source: https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/mincostflow.nim ImportExpand "atcoder/mincostflow" <=== "when not declared ATCODER_MINCOSTFLOW_HPP:\n const ATCODER_MINCOSTFLOW_HPP* = 1\n\n import std/heapqueue\n import std/algorithm\n when not declared ATCODER_INTERNAL_CSR_HPP:\n const ATCODER_INTERNAL_CSR_HPP* = 1\n \n type csr*[E] = object\n start*: seq[int]\n elist*: seq[E]\n proc initCsr*[E](n:int, edges:seq[(int, E)]):csr[E] =\n var start = newSeq[int](n + 1)\n var elist = newSeq[E](edges.len)\n for e in edges: start[e[0] + 1].inc\n for i in 1..n: start[i] += start[i - 1]\n var counter = start\n for e in edges:\n elist[counter[e[0]]] = e[1]\n counter[e[0]].inc\n return csr[E](start:start, elist:elist)\n \n when not declared ATCODER_INTERNAL_QUEUE_HPP:\n const ATCODER_INTERNAL_QUEUE_HPP* = 1\n \n type simple_queue[T] = object\n payload:seq[T]\n pos:int\n proc init_simple_queue*[T]():auto = simple_queue[T](payload:newSeq[T](), pos:0)\n # TODO\n # void reserve(int n) { payload.reserve(n); }\n proc len*[T](self:simple_queue[T]):int = self.payload.len - self.pos\n proc empty*[T](self:simple_queue[T]):bool = self.pos == self.payload.len\n proc push*[T](self:var simple_queue[T], t:T) = self.payload.add(t)\n proc front*[T](self:simple_queue[T]):T = self.payload[self.pos]\n proc clear*[T](self:var simple_queue[T]) =\n self.payload.setLen(0)\n self.pos = 0;\n proc pop*[T](self:var simple_queue[T]) = self.pos.inc\n \n when not declared ATCODER_INTERNAL_HEAP:\n const ATCODER_INTERNAL_HEAP* = 1\n proc push_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n var i = p.b\n while i > 0:\n var p = (i - 1) shr 1\n if v[p] < v[i]: swap v[p], v[i]\n else: break\n i = p\n proc pop_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n swap v[0], v[p.b]\n var p = p\n p.b.dec\n var i = 0\n while true:\n var (c0, c1) = (i * 2 + 1, i * 2 + 2)\n if c1 in p:\n if v[c1] > v[i]:\n if v[c0] > v[c1]:\n swap(v[i], v[c0])\n i = c0\n else:\n swap(v[i], v[c1])\n i = c1\n elif v[c0] > v[i]:\n swap(v[i], v[c0])\n i = c0\n else: break\n elif c0 in p:\n if v[c0] > v[i]:\n swap(v[i], v[c0])\n i = c0\n else: break\n else: break\n \n\n type MCFEdge*[Cap, Cost] = object\n src*, dst*: int\n cap*, flow*: Cap\n cost*: Cost\n\n type MCFInternalEdge[Cap, Cost] = object\n dst, rev: int\n cap: Cap\n cost: Cost\n\n type MCFGraph*[Cap, Cost] = object\n n:int\n edges:seq[MCFEdge[Cap, Cost]]\n \n proc initMCFGraph*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n proc initMinCostFLow*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n\n proc add_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], src, dst:int, cap:Cap, cost:Cost):int {.discardable.} =\n assert src in 0..<self.n\n assert dst in 0..<self.n\n assert 0 <= cap\n assert 0 <= cost\n var m = self.edges.len\n self.edges.add(MCFEdge[Cap, Cost](src:src, dst:dst, cap:cap, flow:0, cost:cost))\n return m\n\n proc get_edge*[Cap, Cost](self:MCFGraph[Cap, Cost], i:int): MCFEdge[Cap, Cost] =\n let m = self.edges.len\n assert i in 0..<m\n return self.edges[i]\n\n proc edges*[Cap, Cost](self:var MCFGraph[Cap, Cost]):seq[MCFEdge[Cap, Cost]] = self.edges\n type MCFQ[Cost] = object\n key:Cost\n dst:int\n proc `<`*[Cost](l, r:MCFQ[Cost]):bool = l.key > r.key\n\n proc slope*[Cap, Cost](self: MCFGraph[Cap, Cost], g:var csr[MCFInternalEdge[Cap, Cost]], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n\n var\n dual_dist = newSeq[tuple[dual, dist:Cost]](self.n)\n prev_e = newSeq[int](self.n)\n vis = newSeq[bool](self.n)\n que_min = newSeq[int]()\n que = newSeq[MCFQ[Cost]]()\n proc dual_ref(g:csr[MCFInternalEdge[Cap, Cost]]):bool =\n for i in 0..<self.n: dual_dist[i].dist = Cost.high\n vis.fill(false)\n que_min.setLen(0)\n que.setLen(0)\n\n # que[0..heap_r) was heapified\n var heap_r = 0\n\n dual_dist[s].dist = 0\n que_min.add(s)\n while que_min.len > 0 or que.len > 0:\n var v:int\n if que_min.len > 0:\n v = que_min.pop()\n else:\n while heap_r < que.len:\n heap_r.inc\n que.push_heap(0 ..< heap_r)\n v = que[0].dst\n que.pop_heap(0 ..< que.len)\n discard que.pop()\n heap_r.dec\n if vis[v]: continue\n vis[v] = true\n if v == t: break\n let (dual_v, dist_v) = dual_dist[v]\n for i in g.start[v] ..< g.start[v + 1]:\n let e = g.elist[i]\n if e.cap == Cap(0): continue\n let cost = e.cost - dual_dist[e.dst].dual + dual_v\n if dual_dist[e.dst].dist - dist_v > cost:\n let dist_to = dist_v + cost\n dual_dist[e.dst].dist = dist_to\n prev_e[e.dst] = e.rev\n if dist_to == dist_v:\n que_min.add(e.dst)\n else:\n que.add(MCFQ[Cost](key:dist_to, dst:e.dst))\n if not vis[t]:\n return false\n\n for v in 0..<self.n:\n if not vis[v]: continue\n # dual[v] = dual[v] - dist[t] + dist[v]\n # = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +\n # (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,\n # t) + dual[t] + shortest(s, v) = shortest(s, v) -\n # shortest(s, t) >= 0 - (n-1)C\n dual_dist[v].dual -= dual_dist[t].dist - dual_dist[v].dist\n return true\n var\n flow:Cap = 0\n cost:Cost = 0\n prev_cost_per_flow:Cost = -1\n result = @[(Cap(0), Cost(0))]\n while flow < flow_limit:\n if not g.dual_ref(): break\n var c = flow_limit - flow\n block:\n var v = t\n while v != s:\n c = min(c, g.elist[g.elist[prev_e[v]].rev].cap)\n v = g.elist[prev_e[v]].dst\n block:\n var v = t\n while v != s:\n var e = g.elist[prev_e[v]].addr\n e[].cap += c\n g.elist[e[].rev].cap -= c\n v = g.elist[prev_e[v]].dst\n let d = -dual_dist[s].dual\n flow += c\n cost += c * d\n if prev_cost_per_flow == d:\n discard result.pop()\n result.add((flow, cost))\n prev_cost_per_flow = d\n\n proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n assert s in 0..<self.n\n assert t in 0..<self.n\n assert s != t\n\n let m = self.edges.len\n var edge_idx = newSeq[int](m)\n\n var g = block:\n var degree = newSeq[int](self.n)\n var redge_idx = newSeq[int](m)\n var elist = newSeqOfCap[(int, MCFInternalEdge[Cap, Cost])](2 * m)\n for i in 0..<m:\n let e = self.edges[i]\n edge_idx[i] = degree[e.src]\n degree[e.src].inc\n redge_idx[i] = degree[e.dst]\n degree[e.dst].inc\n elist.add((e.src, MCFInternalEdge[Cap, Cost](dst: e.dst, rev: -1, cap:e.cap - e.flow, cost:e.cost)))\n elist.add((e.dst, MCFInternalEdge[Cap, Cost](dst: e.src, rev: -1, cap:e.flow, cost: -e.cost)))\n var g = initCSR[MCFInternalEdge[Cap, Cost]](self.n, elist)\n for i in 0..<m:\n let e = self.edges[i]\n edge_idx[i] += g.start[e.src]\n redge_idx[i] += g.start[e.dst]\n g.elist[edge_idx[i]].rev = redge_idx[i];\n g.elist[redge_idx[i]].rev = edge_idx[i];\n g\n\n result = self.slope(g, s, t, flow_limit)\n\n for i in 0..<m:\n let e = g.elist[edge_idx[i]]\n self.edges[i].flow = self.edges[i].cap - e.cap\n proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):tuple[cap:Cap, cost:Cost] = self.slope(s, t, flow_limit)[^1]\n proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):tuple[cap:Cap, cost:Cost] = self.flow(s, t, Cap.high)\n proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):seq[tuple[cap:Cap, cost:Cost]] = self.slope(s, t, Cap.high)\n\n proc reset*[Cap, Cost](self: var MCFGraph[Cap, Cost]) =\n for e in self.edges.mitems:\n e.flow = 0\n\n proc set_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], i:int, cap:Cap, cost:Cost) =\n assert 0 <= cap\n assert 0 <= cost\n var m = self.edges.len\n assert i in 0 ..< m\n edges[i].cap = cap\n edges[i].cost = cost\n" # {.checks: off.} var n,m = input(int) var a = input(int, n, m) proc solve_small_m1() = var k = pow(n, m) var dp = newSeqWith(k, -INFL) dp[0] = 0 for i in 0..<n: var dpn = newSeqWith(k, -INFL) for j in 0..<k: if dp[j] == -INFL: continue dpn[j].max= dp[j] var pw = 1 for d in 0..<m: var k = (j div pw) mod n if k != 0: dpn[j - pw].max= dp[j] + a[i][d] if k != (n-1): dpn[j + pw].max= dp[j] - a[i][d] pw *= n swap(dp, dpn) print(dp[0]) proc solve_small_m2() = var k = n // 2 var al = a[0..<k] var au = a[(^k)..(^1)] var lower = newseqwith(2*k+1, INFL) lower[k] = 0 for i in 0..<k: var ln = newseqwith(2*k+1, INFL) for j in 0..(2*k): if j > 0: ln[j-1].min= lower[j] + al[i][0] if j < 2*k: ln[j+1].min= lower[j] + al[i][1] swap(lower, ln) var upper = newseqwith(2*k+1, -INFL) upper[k] = 0 for i in 0..<k: var un = newseqwith(2*k+1, -INFL) for j in 0..(2*k): if j > 0: un[j-1].max= upper[j] + au[i][0] if j < 2*k: un[j+1].max= upper[j] + au[i][1] swap(upper, un) debug(lower) debug(upper) var ans = 0 for i in 0..2*k: ans.max= upper[i] - lower[i] print(ans) if m == 1: solve_small_m1() quit() elif m == 2: solve_small_m2() quit() var k = n // 2 var g = initmcfgraph[int, int](2 * k + 2) var src = k * 2 var dst = src + 1 for i in 0..<k: g.add_edge(src, i, 1, 0) for i in 0..<k: g.add_edge(i + k, dst, 1, 0) var u = 2_000_000_000 for i in 0..<k: for j in 0..<k: var f = -INFL for t in 0..<m: f.max= a[^(j+1)][t] - a[i][t] debug(i, j, f) g.add_edge(i, j + k, 1, u - f) var (_, cost) = g.flow(src, dst) var ans = u * k - cost print(ans)