結果
| 問題 |
No.957 植林
|
| コンテスト | |
| ユーザー |
 yakamoto
|
| 提出日時 | 2019-12-27 02:03:31 |
| 言語 | Scala(Beta) (3.6.2) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,433 bytes |
| コンパイル時間 | 14,923 ms |
| コンパイル使用メモリ | 280,840 KB |
| 実行使用メモリ | 79,040 KB |
| 最終ジャッジ日時 | 2024-10-05 19:27:41 |
| 合計ジャッジ時間 | 98,368 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 TLE * 23 |
ソースコード
object Main {
import java.io.{BufferedReader, InputStream, InputStreamReader}
import java.util.StringTokenizer
import scala.reflect.ClassTag
def main(args: Array[String]): Unit = {
val out = new java.io.PrintWriter(System.out)
new Main(out, new InputReader(System.in)).solve()
out.flush()
}
private[this] val oj = System.getenv("MY_DEBUG") == null
def DEBUG(f: => Unit): Unit = {
if (!oj){ f }
}
def debug(as: Array[Boolean]): Unit = if (!oj){ debug(as.map(x => if(x) "1" else "0").mkString) }
def debug(as: Array[Int]): Unit = if (!oj){ debug(as.mkString(" ")) }
def debug(as: Array[Long]): Unit =if (!oj){ debug(as.mkString(" ")) }
def debugDim(m: Array[Array[Int]]): Unit = if (!oj){
REP(m.length) { i =>
debug(m(i))
}
}
def debugDimFlip(m: Array[Array[Long]]): Unit = if (!oj){
REP(m(0).length) { j =>
REP(m.length) { i =>
System.err.print(m(i)(j))
System.err.print(" ")
}
System.err.println()
}
}
def debug(s: => String): Unit = {
if (!oj){ System.err.println(s) }
}
def isDebug[A](debug: => A, online: => A): A = {
if (oj) online else debug
}
class InputReader(val stream: InputStream) {
private[this] val reader = new BufferedReader(new InputStreamReader(stream), 32768)
private[this] var tokenizer: StringTokenizer = _
private[this] def next(): String = {
while (tokenizer == null || !tokenizer.hasMoreTokens)
tokenizer = new StringTokenizer(reader.readLine)
tokenizer.nextToken
}
def nextInt(): Int = Integer.parseInt(next())
def nextLong(): Long = java.lang.Long.parseLong(next())
def nextChar(): Char = next().charAt(0)
def ni(): Int = nextInt()
def nl(): Long = nextLong()
def nc(): Char = nextChar()
def ns(): String = next()
def ns(n: Int): Array[Char] = ns().toCharArray
def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
val A1, A2 = Array.ofDim[Int](n)
REP(n) { i =>
A1(i) = ni() + offset
A2(i) = ni() + offset
}
(A1, A2)
}
def nm(n: Int, m: Int): Array[Array[Int]] = {
val A = Array.ofDim[Int](n, m)
REP(n) { i =>
REP(m) { j =>
A(i)(j) = ni()
}
}
A
}
def nal(n: Int): Array[Long] = map(n)(_ => nl())
def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
}
def REP(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
var i = offset
val N = n + offset
while(i < N) { f(i); i += 1 }
}
def REP_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
var i = n - 1 + offset
while(i >= offset) { f(i); i -= 1 }
}
def TO(from: Int, to: Int)(f: Int => Unit): Unit = {
REP(to - from + 1, from)(f)
}
def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
val res = Array.ofDim[A](n)
REP(n)(i => res(i) = f(i + offset))
res
}
def sumL(as: Array[Int]): Long = {
var s = 0L
REP(as.length)(i => s += as(i))
s
}
def cumSum(as: Array[Int]): Array[Long] = {
val cum = Array.ofDim[Long](as.length + 1)
REP(as.length) { i =>
cum(i + 1) = cum(i) + as(i)
}
cum
}
}
object Workspace {
import Main._
import java.util.Arrays.sort
import scala.collection.mutable
import math.{abs, max, min}
import mutable.ArrayBuffer
type A = Long
type Graph = Array[ArrayBuffer[Edge]]
case class Edge(v: Int, w: A)
class Edge2(val to: Int, var cap: A, val rev: Int)
def maxFlow(baseG: Graph, s: Int, t: Int, inf: A): A = {
val n = baseG.length
val level = Array.ofDim[Int](n)
val iter = Array.ofDim[Int](n)
val g = Array.fill[ArrayBuffer[Edge2]](n)(ArrayBuffer())
def addEdge(v: Int, e: Edge): Unit = {
g(v) += new Edge2(e.v, e.w, g(e.v).size)
g(e.v) += new Edge2(v, 0, g(v).size - 1)
}
REP(n) { v =>
REP(baseG(v).length) { j =>
addEdge(v, baseG(v)(j))
}
}
def bfs(s: Int): Unit = {
val queue = new java.util.ArrayDeque[Int]()
level(s) = 0
queue.add(s)
while(!queue.isEmpty) {
val v = queue.poll()
REP(g(v).length) { i =>
val e = g(v)(i)
if (e.cap > 0 && level(e.to) < 0) {
level(e.to) = level(v) + 1
queue.add(e.to)
}
}
}
}
def dfs(v: Int, t: Int, f: A): A = {
if (v == t) {
f
} else {
while(iter(v) < g(v).length) {
val e = g(v)(iter(v))
if (e.cap > 0 && level(v) < level(e.to)) {
val d = dfs(e.to, t, min(f, e.cap))
if (d > 0) {
e.cap -= d
g(e.to)(e.rev).cap += d
return d
}
}
iter(v) += 1
}
0
}
}
var flow: A = 0
var continues = true
while(continues) {
import java.util
util.Arrays.fill(iter, 0)
util.Arrays.fill(level, -1)
bfs(s)
debug(level)
if (level(t) < 0) {
continues = false
} else {
var f: A = 0
while({f = dfs(s, t, inf); f > 0}) {
flow = min(inf, flow + f)
}
}
}
if (flow == inf) -1 else flow
}
}
class Main(out: java.io.PrintWriter, sc: Main.InputReader) {
import sc._
import Main._
import java.util.Arrays.sort
import scala.collection.mutable
import math.{abs, max, min}
import mutable.ArrayBuffer
import Workspace._
// toIntとか+7とかするならvalにしろ
final private[this] val MOD = 1000000007
def solve(): Unit = {
val H, W = ni()
val G = nm(H, W)
val R = na(H)
val C = na(W)
val g = Array.fill[ArrayBuffer[Edge]](H + W + 2)(ArrayBuffer())
val S = H + W
val T = S + 1
val inf = 1e18.toLong
REP(H) { h =>
val id = h
g(S) += Edge(id, max(0, sumL(G(h)) - R(h))) // 儲かるときは0にする
}
REP(W) { w =>
val id = H + w
REP(H) { h =>
g(h) += Edge(id, G(h)(w)) // wが有効 かつ h無効 だとGhw損する
}
g(id) += Edge(T, C(w)) // wが無効だと Cw損
}
val cut = maxFlow(g, S, T, inf)
debug(s"cut:$cut")
val gainH = map(H){ h => max(0, R(h) - sumL(G(h)))}.sum
val gainW = sumL(C)
val ans = max(0, gainH + gainW - cut)
out.println(ans)
}
}