Da es sich um eine Bedingung einer linearen Gleichung handelt, kann die Anzahl der Berechnungen mithilfe des NumPy-Arrays erheblich reduziert werden. Das NumPy-Array verhält sich wie ein Iterable.
Es kann auch mit PyPy ausgeführt und die Berechnungsgeschwindigkeit erhöht werden. (Die Speichernutzung nimmt aus irgendeinem Grund zu.)
Python3 1063 ms 106372 KB PyPy3 571 ms 155196 KB
Beispielcode
import sys
import itertools
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N, M, Q = map(int, readline().split())
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
# [[1 1 1]
# [1 1 2]
# [1 1 3]
# [1 1 4]
# [1 2 2] ...
n = len(A)
score = np.zeros(n, np.int32)
m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
cond = A[:, b - 1] - A[:, a - 1] == c #NumPy-Array
score += d * cond
print(score.max())
Recommended Posts