Submission #17761215


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 << 30

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
    sink = N + 1
    add_minus = [0] * N
    add_plus = [0] * N
    base_score = 0
    for i in range(N):
        a, b = A[i], B[i]
        x, y, z = -a, -b, b  # 破壊、マイナスでとる、プラスでとる
        m = min(x, y, z)
        if m == x:
            mm = max(y, z)
            base_score += mm
            G.add_edge(source, i, capacity=mm - y)
            G.add_edge(i, sink, capacity=mm - z)
            add_minus[i] = add_plus[i] = 1
        elif m == y:
            mm = max(x, z)
            base_score += mm
            G.add_edge(source, i, capacity=mm - x)
            G.add_edge(i, sink, capacity=mm - z)
            add_plus[i] = 1
        elif m == z:
            mm = max(x, y)
            base_score += mm
            G.add_edge(source, i, capacity=mm - y)  # マイナス
            G.add_edge(i, sink, capacity=mm - x)  # こわす
            add_minus[i] = 1
    for i in range(len(UV)):
        u, v = UV[i]
        for _ in range(2):
            u, v = v, u
            if add_minus[u] and add_plus[v]:
                G.add_edge(v, 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 0
Code Size 1818 Byte
Status WA
Exec Time 340 ms
Memory 55012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 2
WA × 1
AC × 18
WA × 36
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 315 ms 52972 KB
00-sample-002.txt WA 308 ms 53340 KB
00-sample-003.txt AC 308 ms 52860 KB
01-001.txt AC 310 ms 53164 KB
01-002.txt AC 312 ms 53524 KB
01-003.txt AC 311 ms 52952 KB
01-004.txt AC 311 ms 53356 KB
01-005.txt AC 309 ms 53036 KB
01-006.txt AC 309 ms 53056 KB
01-007.txt AC 316 ms 54008 KB
01-008.txt AC 314 ms 53820 KB
01-009.txt AC 315 ms 53376 KB
01-010.txt AC 314 ms 53616 KB
01-011.txt AC 316 ms 53828 KB
01-012.txt AC 314 ms 54024 KB
01-013.txt AC 316 ms 53428 KB
01-014.txt AC 316 ms 54196 KB
01-015.txt WA 317 ms 53776 KB
01-016.txt AC 312 ms 53648 KB
01-017.txt AC 317 ms 53620 KB
01-018.txt WA 322 ms 53836 KB
01-019.txt WA 319 ms 54192 KB
01-020.txt WA 318 ms 53880 KB
01-021.txt WA 315 ms 53612 KB
01-022.txt WA 315 ms 54084 KB
01-023.txt WA 317 ms 54112 KB
01-024.txt WA 328 ms 53920 KB
01-025.txt WA 321 ms 53704 KB
01-026.txt WA 330 ms 54456 KB
01-027.txt WA 326 ms 54288 KB
01-028.txt WA 324 ms 54224 KB
01-029.txt WA 331 ms 54056 KB
01-030.txt WA 334 ms 54456 KB
01-031.txt WA 323 ms 53704 KB
01-032.txt WA 329 ms 53784 KB
01-033.txt WA 325 ms 53716 KB
01-034.txt WA 328 ms 54408 KB
01-035.txt WA 326 ms 54000 KB
01-036.txt WA 324 ms 54452 KB
01-037.txt WA 335 ms 53980 KB
01-038.txt WA 324 ms 54372 KB
01-039.txt WA 330 ms 54020 KB
01-040.txt WA 330 ms 54352 KB
01-041.txt WA 333 ms 54144 KB
01-042.txt WA 336 ms 55012 KB
01-043.txt WA 334 ms 54816 KB
01-044.txt WA 331 ms 54332 KB
01-045.txt WA 334 ms 54880 KB
01-046.txt WA 336 ms 54800 KB
01-047.txt WA 337 ms 54732 KB
01-048.txt WA 332 ms 54772 KB
01-049.txt WA 339 ms 54732 KB
01-050.txt WA 336 ms 54768 KB
01-051.txt WA 340 ms 54528 KB