Since it is a condition of a linear equation, the number of calculations can be greatly reduced by using a NumPy array. The NumPy array acts like an iterable.
It can also be executed with PyPy, and the calculation speed can be increased. (Memory usage increases for some reason)
Python3 1063 ms 106372 KB PyPy3 571 ms 155196 KB
Sample code
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