Puisqu'il s'agit d'une condition d'une équation linéaire, le nombre de calculs peut être considérablement réduit en utilisant le tableau NumPy. Le tableau NumPy agit comme un itérable.
Il peut également être exécuté avec PyPy et la vitesse de calcul peut être augmentée. (L'utilisation de la mémoire augmente pour une raison quelconque)
Python3 1063 ms 106372 KB PyPy3 571 ms 155196 KB
Exemple de 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 #Tableau NumPy
score += d * cond
print(score.max())
Recommended Posts