Problem: Given are positive integers N, M, Q, and Q quadruples of integers ( a_i , b_i , c_i , d_i ).  Consider a sequence A satisfying the following conditions:    * A is a sequence of N positive integers.   * 1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.  Let us define a score of this sequence as follows:    * The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i. (If there is no such i, the score is 0.)  Find the maximum possible score of A.

Submission attempts (in order):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    if ans < cnt:
        ans = cnt
print(ans)

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))
n, m, q = map(int, input().split())
vec = [0]
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(m):
    for j in range(len(it) - 1): vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]: na.append(j)
        if b[i] == it[j]: nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]: cnt += d[i]
    if ans < cnt: ans = cnt
print(ans)

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = [1]
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it) - 1):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))

n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)


import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 
# list(map(int, input().split()))

n, m, q = map(int, input().split(' '))
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    if ans < cnt:
        ans = cnt
print(ans)

Verdicts: Runtime Error

Time Limit Exceeded

Runtime Error

Time Limit Exceeded

Time Limit Exceeded

Runtime Error

Accepted