Problem:


Score : 300 points

Problem Statement

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.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )

0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )

(a_i, b_i, c_i) \neq (a_j, b_j, c_j) (where i \neq j)

1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )

Input

Input is given from Standard Input in the following format:

N M Q
a_1 b_1 c_1 d_1
:
a_Q b_Q c_Q d_Q

Output

Print the maximum possible score of A.

Sample Input 1

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10

Sample Output 1

110

When A = \{1, 3, 4\}, its score is 110. Under these conditions, no sequence has a score greater than 110, so the answer is 110.

Sample Input 2

4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



Sample input:
3 4 3
1 3 3 100
1 2 2 10
2 3 2 10


Sample output:
110

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
#めっちゃfor分あるならdfs
R=[range(i,m) for i in range(m)]
def dfs(d,s):
    global n,m,Q,ans
    if d==n:
        ans_=0
        for k in Q:
            a,b,c,e=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=e
        ans=max(ans,ans_)
    else:
        l=int(s[-1])
        for i in R[l]:
            dfs(d+1,s+str(i))
for i in R[0]:
    dfs(1,str(i))

print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]

def gen_list(li, n, m):
    if len(li[0]) == n:
        return li
    
    res = []
    for d in li:
        base = [i for i in range(d[-1], m+1)]
        for x in base:
            tmp = d.copy()
            tmp.append(x)
            res.append(tmp)
    return gen_list(res, n, m)

base = [[i] for i in range(1, m+1)]
A_list = gen_list(base, n, m)
ans = 0
for A in A_list:
    tmp = 0
    for d in query:
        if A[d[1]-1] - A[d[0]-1] == d[2]:
            tmp += d[3]
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import itertools


n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    queries.append((a-1, b-1, c, d))

patterns = itertools.combinations_with_replacement(range(1, m+1), n)

candidates = []
for pattern in patterns:
    res = 0
    for a, b, c, d in queries:
        if int(pattern[b]) - int(pattern[a]) == c:
            res += d

    candidates.append(res)

print(max(candidates))

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(q)]
#print(s)

maxi = 0
#l = [1,2,3,4,5,6,7,8,9,10]
l = []
for i in range(m):
	l.append(i)
#print(l)
for a in itertools.combinations_with_replacement(l, n):
	#print(a)
	pnt = 0
	for i in range(q):
		#print(s[i][1]-1,s[i][0]-1)

		if a[s[i][1]-1]-a[s[i][0]-1] == s[i][2]:
			#print(a[s[i][1]-1],a[s[i][0]-1] )
			
			pnt += s[i][3]
	#print(pnt)
	if pnt >maxi:
		maxi = pnt
		#print(a)
print(maxi)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
L = []
for i in range(Q):
    L.append(list(map(int, input().split())))
 
def f(s):
    if len(s) == N:
        return [s]
    yy = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        yy.extend(f(s + str(i)))
    return yy
 
ans = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in L:
        if A[b - 1] - A[a - 1] == c:
            t += d
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, M, Q = map(int, input().split())

point = [list(map(int, input().split())) for _ in range(Q)]


def A_generator():
    q = deque()
    q.append([1])
    while len(q) > 0:
        a = q.pop()
        if len(a) < N + 1:
            for i in range(a[-1], M + 1):
                q.append(a + [i])
        else:
            yield a


ans = 0

for A in A_generator():
    point_sum = 0
    for p in point:
       if A[p[1]] - A[p[0]] == p[2]:
            point_sum += p[3]

    ans = max(ans, point_sum)

print(ans)

Submission status: Accepted

Solution code:
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == N:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max(solve(A + [i]) for i in range(A[-1], M + 1))

print(solve([1]))

Submission status: Accepted

Solution code:
n, m, q = map(int,input().split())
abcd = []
for _ in range(q):
    abcd.append(list(map(int,input().split())))

a_l = [1] * n
ans = 0
while True:
    ans_tmp = 0
    for a, b, c, d in abcd:
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    if a_l == [m]*n:
        break
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break
    for i in range(1,n):
        while a_l[i-1] > a_l[i]:
            a_l[i] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

## コンテスト中に書いたコード

N, M, Q = mi()
abcd = li2(Q)

a = '0' * N
m = str(M-1)
l = [a]

while True:
    i = N-1
    while i >= 0 and a[i] == m: #更新する桁を探索
        i -= 1
    if i == -1:
        break
    a = list(a) #strのままだと書き込めないから一旦リストに変換
    num = str(int(a[i]) + 1) #更新する桁を探索
    a[i] = num
    if i != N-1:
        for j in range(i+1, N): #更新する桁が新しくなった場合、それ以降の桁の値も揃える。Ex)11199 → 11222
            a[j] = num
    tmp = ''.join(a) #文字列に戻す
    l.append(tmp)

ans = 0
for num in l:
    cnt = 0
    #num = list(map(int, list(num)))
    for i in range(Q):
        if int(num[abcd[i][1]-1]) - int(num[abcd[i][0]-1]) == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
res = 0

def dfs(A):
    global res
    if len(A) == N:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                tmp += d
        if tmp > res:
            res = tmp
        return

    if len(A) == 0:
        d = 1
    else:
        d = A[-1]

    for i in range(d, M+1):
        dfs(A + [i])

dfs([])
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N,M,Q = (int(x) for x in input().split())
q = []
Max = 0
for i in range(Q):
    q.append(list(map(int, input().split())))
for x in combinations_with_replacement(range(1,M+1),N):
    temp = 0
    for y in q:
        if x[y[1]-1] - x[y[0]-1] == y[2]:
            temp += y[3]
    Max = max(temp,Max)
print(Max)

Submission status: Accepted

Solution code:
import itertools


def main():
    n,m,q = map(int,input().split())
    C_list = [list(map(int,input().split())) for _ in range(q)]

    A_list = itertools.combinations_with_replacement(range(1,m+1),n)
    ans = 0
    for A in A_list:
        tmp = 0
        for C in C_list:
            if A[C[1]-1]-A[C[0]-1] == C[2]:
                tmp += C[3]
        ans = max(ans,tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
def main():
    #入力
    readline=stdin.readline
    N,M,Q=map(int,readline().split())
    a=[]
    b=[]
    c=[]
    d=[]
    for i in range(Q):
        li=list(map(int,readline().split()))
        a.append(li[0])
        b.append(li[1])
        c.append(li[2])
        d.append(li[3])

    li_2=list(itertools.combinations_with_replacement(list(range(1,M+1)),N))
    
    max_res=0
    for i in range(len(li_2)):
        A=li_2[i]
        res=0
        for j in range(Q):
            if A[b[j]-1]-A[a[j]-1]==c[j]:
                res+=d[j]
        max_res=max(max_res,res)
    print(max_res)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N, M ,Q = map(int, input().split())
l = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  l.append([a, b, c, d])
  
nums = list(itertools.combinations_with_replacement(range(1, M+1), N))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]-1]-row[l[i][0]-1] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from itertools import combinations_with_replacement

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, Q = lr()
ABCD = [lr() for _ in range(Q)]
answer = 0
for x in combinations_with_replacement(range(1, M+1), N):
    temp = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            temp += d
    if temp > answer:
        answer = temp

print(answer)
#05

Submission status: Accepted

Solution code:
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score = 0
        for a, b, c, d in req:
            if nums[b] - nums[a] == c:
                score += d
        return score
    else:
        for next_num in range(min_lim, m + 1):
            nums[length + 1] = next_num
            s = dfs(nums, length + 1, next_num)
            ans = max(ans, s)
    return ans


n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]

# 添字がわかりづらくなるので、n+1個のリストを用意します
nums = [0] * (n + 1)

ans = dfs(nums, 0, 1)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m,q = list(map(int,input().split()))
abcd =  [list(map(int,input().split())) for i in range(q)]


def dfs(x,y,z,que):
    ret = 0
    if x == 0:
        for a,b,c,d in abcd:
            if que[b-1] - que[a-1]==c:
                ret+=d
        return ret
    for i in range(y,z+1):
        ret = max(ret,dfs(x-1,i,z,que + [i]))
    return ret

print(dfs(n,1,m,[]))

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations_with_replacement

    N, M, Q = map(int, input().split())

    conds = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        conds.append((a, b, c, d))

    ans = 0
    for temp_A in combinations_with_replacement(iterable=range(1, M + 1), r=N):
        # print(*temp_A)
        t = 0
        for ai, bi, ci, di in conds:
            c = temp_A[bi] - temp_A[ai]
            if c == ci:
                t += di
        ans = max(ans, t)
    print(ans)


if __name__ == '__main__':
    main()

# def choose(n, r):
#     ret = 1
#     for i in range(r):
#         ret *= n - i
#     for i in range(r):
#         ret //= (i + 1)
#     print(ret)
#
# print(choose(20, 10))
# # 184756

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

qq=deque()
for m in range(1,M+1):
    q=deque()
    q.append([m])
    while q:
        if N<len(q[0]):
            qq+=q
            break
        fro=q.popleft()
        last=fro[-1]
        for to in range(last,M+1):
            q.append(fro+[to])

ans=float("-inf")
for L in qq:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
q_list = []
final_score = 0
for i in range(Q):
    q_list.append(list(map(int, input().split())))
for A in itertools.combinations_with_replacement(range(1,M+1), N):
    score = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            score += q[3]
        final_score = max([final_score, score])
print(final_score)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())

nums = []
for _ in range(q):
    nums.append(list(map(int, input().split())))

total = 0

l = [1,2,3,4,5,6,7,8,9,10,11]
for v in itertools.combinations_with_replacement(range(1, m+1), n):
    scores = []
    for a,b,c,d in nums:
        if v[b-1]-v[a-1] == c:
            scores.append(d)
        else:
            scores.append(0)
    if total < sum(scores):
        total = sum(scores)

print(total)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
zz = [list(map(int, input().split())) for _ in range(Q)]

def f(s):
    if len(s) == N:
        return [s]
    result = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        result.extend(f(s + str(i)))
    return result

ans = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in zz:
        if A[b - 1] - A[a - 1] == c:
            t += d
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
 
n,m,q = map(int, input().split())
 
ql = [list(map(int,input().split())) for _ in range(q)]
 
#print(n)
#print(m)
#print(q)
#pprint(ls)
 
masterlist = []
minilist = [0] * n
i = 0
 
 
def saiki(before_a,i,minilist):
    if i > n-1:
        masterlist.append([minilist[j] for j in range(n)])
        return
    for Ai in range(before_a,m+1):
        minilist[i] = Ai
        saiki(Ai,i+1,minilist)
 
#for before_a in range(1,m+1):
#    saiki(before_a,where,minilist)
 
before_a = 1
saiki(before_a,i,minilist)
 
#pprint(masterlist)
#pprint(ql)
 
dmax = 0
 
for a_mini in masterlist:
    dtemp = 0
    for ql_mini in ql:
        if a_mini[ql_mini[1]-1] - a_mini[ql_mini[0]-1] == ql_mini[2]:
            dtemp += ql_mini[3]
        else:
            pass
    if dtemp >= dmax:
        dmax = dtemp
 
print(dmax)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
def score_check(A,L):
    point = 0
    for a, b, c, score in L:
        temp = A[b - 1] - A[a - 1]
        if temp == c:point += score

    return point

n, m, q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(q)]

num = 0
nums = list(range(1, m + 1))
for i in combinations_with_replacement(nums, n):
    #print(i)
    temp = score_check(i, l)
    if num < temp:num = temp
print(num)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for a in range(1, m + 1):
    for b in range(a, m + 1):
        for c in range(b, m + 1):
            for d in range(c, m + 1):
                for e in range(d, m + 1):
                    for f in range(e, m + 1):
                        for g in range(f, m + 1):
                            for h in range(g, m + 1):
                                for i in range(h, m + 1):
                                    for j in range(i, m + 1):
                                        s = [0, a, b, c, d, e, f, g, h, i, j]
                                        cnt = 0
                                        for w, x, y, z in abcd:
                                            if s[x] - s[w] == y:
                                                cnt += z
                                        ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(Q)]
num = list(combinations_with_replacement(range(1, M+1), N))
ans = 0
for item in num:
    score = 0
    for a,b,c,d in data:
        if item[b-1]-item[a-1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,q = map(int,input().split())
E = [tuple(map(int,input().split())) for i in range(q)]
A = list(itertools.combinations_with_replacement(range(1,m+1),n))
for comb in A:
  tmp = 0
  for a,b,c,d in E:
    a-=1;b-=1
    if comb[b]-comb[a] == c:
      tmp += d
  ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np


def judge(li, T):
    answer = 0
    for i in range(Q):
        a, b, c, d = T[i]
        if li[b - 1] - li[a - 1] == c:
            answer += d
            # print(d)
    return answer


N, M, Q = map(int, input().split())
ans = 0
T = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    T.append([a, b, c, d])


num = list(np.arange(M) + 1)
# print(num)

for tup in itertools.combinations_with_replacement(num, N):
    # num(配列)内のN個分タプルを返す
    # print(df)

    li = list(tup)
    f = judge(li, T)
    ans = max(ans, f)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, q = map(int, input().split())
l = []
ans = 0
ref = 0

for i in range(q):
    abcd = list(map(int, input().split()))
    l.append(abcd)

for i in itertools.combinations_with_replacement(range(1, m + 1), n):
    for a, b, c, d in l:
        if i[b - 1] - i[a - 1] == c:
            ref += d
    ans = max(ans, ref)
    ref = 0

print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    n,m,q = map(int,input().split(" "))
    ops = []
    for i in range(q):
        ops.append(list(map(int,input().split(" "))))
    
    ans = 0
    for A in itertools.combinations_with_replacement(range(1,m+1),n):
        temp = 0
        for op in ops:
            if A[op[1]-1] - A[op[0]-1] == op[2]:
                temp+=op[3]
        ans = max(ans,temp)
    
    print(ans)
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

qq=deque()
for m in range(1,M+1):
    q=deque()
    q.append([m])
    while q:
        if N<len(q[0]):
            qq+=q
            break
        fro=q.popleft()
        last=fro[-1]
        for to in range(last,M+1):
            q.append(fro+[to])

ans=float("-inf")
for L in qq:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Accepted

Solution code:
from pprint import pprint

n,m,q = map(int, input().split())

ql = [list(map(int,input().split())) for _ in range(q)]

#print(n)
#print(m)
#print(q)
#pprint(ls)

masterlist = []
minilist = [0] * n
i = 0


def saiki(before_a,i,minilist):
    if i > n-1:
        masterlist.append([minilist[j] for j in range(n)])
        return
    for Ai in range(before_a,m+1):
        minilist[i] = Ai
        saiki(Ai,i+1,minilist)

#for before_a in range(1,m+1):
#    saiki(before_a,where,minilist)

before_a = 1
saiki(before_a,i,minilist)

#pprint(masterlist)
#pprint(ql)

dmax = 0

for a_mini in masterlist:
    dtemp = 0
    for ql_mini in ql:
        if a_mini[ql_mini[1]-1] - a_mini[ql_mini[0]-1] == ql_mini[2]:
            dtemp += ql_mini[3]
        else:
            pass
    if dtemp >= dmax:
        dmax = dtemp

print(dmax)

Submission status: Accepted

Solution code:
# n,m,q = map(int,input().split())
# q_dic = dict()
# for i in range(1, n):
#     for j in range(i+1, n+1):
#         q_dic[(i,j)] = [0]*m
# for i in range(q):
#     a,b,c,d = map(int,input().split())
#     q_dic[(a,b)][c] = d
# dp = []
# for i in range(n+1):
#     dp.append([0]*(m+1))
# print(dp)
# for i in range(1, n):
#     for j in range(i+1, n+1):
#         tar = q_dic[(i,j)]
#         print(tar)
#         for k in range(len(tar)):
#             for l in range(m+1):
#                 dp[j][k] = dp[i][l] + tar[k]
# print(dp)
#
import itertools
def combination_with_replace_all(seq, choice):
    return list(itertools.combinations_with_replacement(seq, choice))

n,m,q = map(int,input().split())
query = []
ans = -1
for i in range(q):
    a,b,c,d = map(int,input().split())
    query.append((a,b,c,d))
cond = combination_with_replace_all([i for i in range(1,m+1)], n)
for i in range(len(cond)):
    cond_ar = cond[i]
    cnt = 0
    for j in range(q):
        if cond_ar[query[j][1]-1] - cond_ar[query[j][0]-1] == query[j][2]:
            cnt += query[j][3]
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    N, M, Q = map(int, readline().split())
    qlist = []
    for _ in range(Q):
        qlist.append(tuple(map(int, readline().split())))

    iters = itertools.combinations_with_replacement(range(1, M+1), N)
    score = []
    for i in iters:
        stmp = 0
        for q in qlist:
            a = q[0]-1; b = q[1]-1
            if i[b] - i[a] == q[2]:
                stmp += q[3]
        score.append(stmp)
    
    ans = max(score)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])",
from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_score(arr):
        current_score = 0
        for i, j, dist, score in L:
            if arr[j] - arr[i] == dist:
                current_score += score
        return current_score
    
    
    n, m, q = mi()
    L = []
    for _ in range(q):
        a, b, c, d = mi()
        L.append([a-1, b-1, c, d])
    
    ans = 0
    for number_array in combinations_with_replacement(range(1, m + 1), n):
        ans = max(ans, calc_score(number_array))

    print(ans)
                         

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, p = map(int, input().split())
A = []
B = []
C = []
D = []
maximum = 0
for i in range(p):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
for z in range(m):
    for y in range(z, m):
        if n > 2:
            for x in range(y, m):
                if n > 3:
                    for w in range(x, m):
                        if n > 4:
                            for v in range(w, m):
                                if n > 5:
                                    for u in range(v, m):
                                        if n > 6:
                                            for t in range(u, m):
                                                if n > 7:
                                                    for s in range(t, m):
                                                        if n > 8:
                                                            for r in range(s, m):
                                                                if n > 9:
                                                                    for q in range(r, m):
                                                                        L = [z, y, x, w, v, u, t, s, r, q]
                                                                        a = 0
                                                                        for l in range(p):
                                                                            if L[B[l]-1]-L[A[l]-1] == C[l]:
                                                                                a += D[l]
                                                                        maximum = max(maximum, a)
                                                                else:
                                                                    L = [z, y, x, w, v, u, t, s, r]
                                                                    a = 0
                                                                    for l in range(p):
                                                                        if L[B[l]-1]-L[A[l]-1] == C[l]:
                                                                            a += D[l]
                                                                    maximum = max(maximum, a)
                                                        else:
                                                            L = [z, y, x, w, v, u, t, s]
                                                            a = 0
                                                            for l in range(p):
                                                                if L[B[l]-1]-L[A[l]-1] == C[l]:
                                                                    a += D[l]
                                                            maximum = max(maximum, a)
                                                else:
                                                    L = [z, y, x, w, v, u, t]
                                                    a = 0
                                                    for l in range(p):
                                                        if L[B[l]-1]-L[A[l]-1] == C[l]:
                                                            a += D[l]
                                                    maximum = max(maximum, a)
                                        else:
                                            L = [z, y, x, w, v, u]
                                            a = 0
                                            for l in range(p):
                                                if L[B[l]-1]-L[A[l]-1] == C[l]:
                                                    a += D[l]
                                            maximum = max(maximum, a)
                                else:
                                    L = [z, y, x, w, v]
                                    a = 0
                                    for l in range(p):
                                        if L[B[l]-1]-L[A[l]-1] == C[l]:
                                            a += D[l]
                                    maximum = max(maximum, a)
                        else:
                            L = [z, y, x, w]
                            a = 0
                            for l in range(p):
                                if L[B[l]-1]-L[A[l]-1] == C[l]:
                                    a += D[l]
                            maximum = max(maximum, a)
                else:
                    L = [z, y, x]
                    a = 0
                    for l in range(p):
                        if L[B[l]-1]-L[A[l]-1] == C[l]:
                            a += D[l]
                    maximum = max(maximum, a)
        else:
            L = [z, y]
            a = 0
            for l in range(p):
                if L[B[l]-1]-L[A[l]-1] == C[l]:
                    a += D[l]
            maximum = max(maximum, a)
print(maximum)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N,M,Q = map(int,input().split())

comb = list(combinations_with_replacement(range(1,M+1),N))

abcd = []
for i in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append([a-1,b-1,c,d])

ans = 0
for i in comb:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b] - i[a] == c:
            tmp += d
    ans = max(ans,tmp)

print(ans)