Submission #17763834


Source Code Expand

Copy
import sys
import numpy as np
import networkx as nx

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 1 << 50

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def main(N, M, A, B, UV):
    UV = UV - 1
    G = nx.DiGraph()
    source = N + N
    sink = N + N + 1
    base_score = 0
    for i in range(N):
        a, b = A[i], B[i]
        x, y, z = -b, -a, b
        m = max(x, y, z)
        base_score += m
        G.add_edge(source, i, capacity=m - x)
        G.add_edge(i, i + N, capacity=m - y)
        G.add_edge(i + N, sink, capacity=m - z)
        G.add_edge(i + N, i, capacity=INF)
    for i in range(len(UV)):
        u, v = UV[i]
        for _ in range(2):
            u, v = v, u
            G.add_edge(v + N, u, capacity=INF)

    flow = nx.maximum_flow_value(G, source, sink)
    return base_score - flow

N, M = map(int, readline().split())
A = from_readline()
B = from_readline()
G = from_read().reshape(M, 2)

print(main(N, M, A, B, G))

Submission Info

Submission Time
Task F - Sum of Abs
User maspy
Language Python (3.8.2)
Score 900
Code Size 1213 Byte
Status AC
Exec Time 388 ms
Memory 56204 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 54
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt
All 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt, 01-021.txt, 01-022.txt, 01-023.txt, 01-024.txt, 01-025.txt, 01-026.txt, 01-027.txt, 01-028.txt, 01-029.txt, 01-030.txt, 01-031.txt, 01-032.txt, 01-033.txt, 01-034.txt, 01-035.txt, 01-036.txt, 01-037.txt, 01-038.txt, 01-039.txt, 01-040.txt, 01-041.txt, 01-042.txt, 01-043.txt, 01-044.txt, 01-045.txt, 01-046.txt, 01-047.txt, 01-048.txt, 01-049.txt, 01-050.txt, 01-051.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 345 ms 53072 KB
00-sample-002.txt AC 336 ms 53064 KB
00-sample-003.txt AC 337 ms 52972 KB
01-001.txt AC 335 ms 52960 KB
01-002.txt AC 335 ms 52784 KB
01-003.txt AC 339 ms 52984 KB
01-004.txt AC 336 ms 53040 KB
01-005.txt AC 338 ms 52956 KB
01-006.txt AC 333 ms 52888 KB
01-007.txt AC 344 ms 53624 KB
01-008.txt AC 347 ms 53608 KB
01-009.txt AC 344 ms 54172 KB
01-010.txt AC 349 ms 53852 KB
01-011.txt AC 345 ms 53732 KB
01-012.txt AC 350 ms 54556 KB
01-013.txt AC 348 ms 53860 KB
01-014.txt AC 350 ms 54064 KB
01-015.txt AC 350 ms 54792 KB
01-016.txt AC 345 ms 54332 KB
01-017.txt AC 355 ms 54052 KB
01-018.txt AC 358 ms 54620 KB
01-019.txt AC 350 ms 54444 KB
01-020.txt AC 352 ms 54892 KB
01-021.txt AC 346 ms 54216 KB
01-022.txt AC 350 ms 54272 KB
01-023.txt AC 356 ms 54632 KB
01-024.txt AC 364 ms 54760 KB
01-025.txt AC 361 ms 54788 KB
01-026.txt AC 363 ms 55120 KB
01-027.txt AC 369 ms 55168 KB
01-028.txt AC 350 ms 54480 KB
01-029.txt AC 360 ms 54372 KB
01-030.txt AC 358 ms 54596 KB
01-031.txt AC 355 ms 54976 KB
01-032.txt AC 354 ms 54468 KB
01-033.txt AC 353 ms 54340 KB
01-034.txt AC 359 ms 55104 KB
01-035.txt AC 355 ms 54748 KB
01-036.txt AC 359 ms 54500 KB
01-037.txt AC 371 ms 54808 KB
01-038.txt AC 376 ms 55372 KB
01-039.txt AC 379 ms 55460 KB
01-040.txt AC 372 ms 55148 KB
01-041.txt AC 380 ms 55256 KB
01-042.txt AC 383 ms 55776 KB
01-043.txt AC 378 ms 56124 KB
01-044.txt AC 378 ms 55652 KB
01-045.txt AC 383 ms 56164 KB
01-046.txt AC 381 ms 55156 KB
01-047.txt AC 378 ms 55964 KB
01-048.txt AC 379 ms 55940 KB
01-049.txt AC 388 ms 56064 KB
01-050.txt AC 383 ms 56204 KB
01-051.txt AC 383 ms 55876 KB