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:
import numpy as np
import math
import scipy
import itertools

def score(arr):
    hoge = 0
    for ai,bi,ci,di in zip(a, b, c, d):
        if arr[bi-1]-arr[ai-1] == ci:
            hoge += di
    return hoge

def dfs(arr):
    if len(arr) == n:
        return score(arr)
    last = arr[-1] if len(arr) > 0 else 0
    res = 0
    for i in range(last, m):
        arr.append(i)
        res = max(res, dfs(arr))
        arr.pop()
    return res

def solve():
    global a, b, c, d, n, m, q
    n, m, q = map(int, input().split())
    a, b, c, d = [0]*q, [0]*q, [0]*q, [0]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    print(dfs([]))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    score = 0

    def dfs(l, **kwargs):
        N = kwargs['N']
        M = kwargs['M']
        ABCD = kwargs['ABCD']

        # 末端まで探索したか判定
        if judge_end(l, N=N):
            nonlocal score
            tmp_score = calc_score(l, ABCD=ABCD)
            score = max(tmp_score, score)
            return
        else:
            # 現時点から選べる選択肢の列挙と探索
            nexts = listup_next(l[-1], M=M)
            for x in nexts:
                dfs(l+[x], N=N, M=M, ABCD=ABCD)

    def judge_end(l, **kwargs):
        N = kwargs['N']
        return len(l) == N

    def calc_score(l, **kwargs):
        ABCD = kwargs['ABCD']
        s = 0
        for a, b, c, d in ABCD:
            if l[b-1] - l[a-1] == c:
                s += d
        return s

    def listup_next(now, **kwargs):
        m = now
        M = kwargs['M']
        return range(m, M+1)

    for i in range(1, M+1):
        dfs([i], N=N, M=M, ABCD=ABCD)
    print(score)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    score = 0

    def dfs(l, N, M, ABCD):
        # 末端まで探索したか判定
        if judge_end(l, N):
            nonlocal score
            tmp_score = calc_score(ABCD, l)
            score = max(tmp_score, score)
            return
        else:
            # 現時点から選べる選択肢の列挙と探索
            nexts = listup_next(l[-1], M)
            for x in nexts:
                dfs(l+[x], N, M, ABCD)

    def judge_end(l, N):
        return len(l) == N

    def calc_score(ABCD, l):
        s = 0
        for a, b, c, d in ABCD:
            if l[b-1] - l[a-1] == c:
                s += d
        return s

    def listup_next(m, M):
        return range(m, M+1)

    for i in range(1, M+1):
        dfs([i], N, M, ABCD)
    print(score)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
score = 0
def main():

    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    global score
    for i in range(1, M+1):
        dfs([i], N, M, ABCD)
    print(score)


def dfs(l, N, M,ABCD):
    # 末端まで探索したか判定
    if judge_end(l, N):
        global score
        tmp_score = calc_score(ABCD, l)
        score = max(tmp_score, score)
        return
    else:
        # 現時点から選べる選択肢の列挙と探索
        nexts = listup_next(l[-1], M)
        for x in nexts:
            dfs(l+[x], N, M, ABCD)


def judge_end(l, N):
    return len(l) == N


def calc_score(ABCD, l):
    s = 0
    for a, b, c, d in ABCD:
        if l[b-1] - l[a-1] == c:
            s += d
    return s


def listup_next(m, M):
    return range(m, M+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
import scipy
import itertools

def score(arr):
    hoge = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if arr[bi-1] - arr[ai-1] == ci:
            hoge += di
    return hoge

def dfs(arr):
    if len(arr) == n:
        return score(arr)
    res = 0
    prev_last = arr[-1] if len(arr) > 0 else 0
    for v in range(prev_last, m):
        arr.append(v)
        res = max(res, dfs(arr))
        arr.pop()
    return res

def solve():
    global a, b, c, d, n, m, q
    n, m, q = map(int, input().split())
    a, b, c, d = [0]*q, [0]*q, [0]*q, [0]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    print(dfs([]))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:


def dfs(l,N,M):
    # 末端まで探索したか判定
    if judge_end(l,N):
        global score
        
        tmp_score = calc_score(ABCD,l)
        score = max(tmp_score, score)
        return
    else:
        # 現時点から選べる選択肢の列挙と探索
        nexts = listup_next(l[-1], M)
        for x in nexts:
            dfs(l+[x],N,M)


def judge_end(l,N):
    return len(l)==N


def calc_score(ABCD, l):
    s=0
    for a,b,c,d in ABCD:
      if l[b-1] - l[a-1] ==c:
        s+=d
    return s


def listup_next(m, M):
    return range(m,M+1)

N,M,Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for i in range(Q)]
score=0
for i in range(1, M+1):
  dfs([i], N,M)
print(score)

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(a):
    def func(a):
        if len(a) == N + 1:
            now = 0
            for i in range(Q):
                if a[B[i]] - a[A[i]] == C[i]:
                    now += D[i]
            addn(now)
            return

        a = a + [a[-1]]
        while a[-1] <= M:
            func(a)
            a[-1] += 1

    ret = set()
    addn = ret.add
    func(a)
    return max(ret)


def main():
    ans = dfs([1])
    print(ans)


input = lambda: stdin.readline()[:-1]
N, M, Q = map(int, input().split())
A, B, C, D = zip(*[map(int, input().split()) for _ in [0] * Q])
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from copy import copy
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]

    def dfs(num_list):
        if len(num_list) == N:
            nonlocal s
            tmp_s = 0
            for a, b, c, d in ABCD:
                if num_list[b-1] - num_list[a-1] == c:
                    tmp_s += d
            s = max(tmp_s, s)

            return
        else:
            for i in range(num_list[-1], M+1):
                dfs(num_list+[i])

    s = 0
    for i in range(1, M+1):
        dfs([i])
    print(s)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

s = 0


def main():
    import sys
    from copy import copy
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]

    def dfs(num_list):
        if len(num_list) == N:
            global s
            tmp_s = 0
            for a, b, c, d in ABCD:
                if num_list[b-1] - num_list[a-1] == c:
                    tmp_s += d
            s = max(tmp_s, s)

            return
        else:
            for i in range(num_list[-1], M+1):
                dfs(num_list+[i])

    for i in range(1, M+1):
        dfs([i])
    print(s)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
e = [list() for _ in range(n)]
for _ in range(q):
    a, b, c, d = map(int, input().split())
    e[b - 1].append((a - 1, c, d))
a = [0] * n
ans = 0
cur = 0
def dfs(u):
    global cur, ans
    if u >= n:
        ans = max(ans, cur)
        return
    for i in range(a[u - 1] if u else 1, m + 1):
        a[u] = i
        for b, c, d in e[u]:
            if i - a[b] == c:
                cur += d
        dfs(u + 1)
        for b, c, d in e[u]:
            if i - a[b] == c:
                cur -= d
dfs(0)
print(ans)

Submission status: Accepted

Solution code:
import copy

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

for i in range(Q) :
    a,b,c,d = map(int, input().split())
    dataList.append([a,b,c,d])
ans = 0
    
def dfs(A) :
    global ans
    if(len(A) == N+1) :
#         print(A)
        now = 0
        for i in range(Q):
            if(A[dataList[i][1]] - A[dataList[i][0]] == dataList[i][2]) :
                now += dataList[i][3]
        ans = max(ans,now)
        return 0

    A.append(A[-1])
    while(A[-1] <= M) :
        dfs(copy.copy(A))
        A[-1]+=1
        
        



dfs([1])
print(ans)

Submission status: Accepted

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

def dfs(num_l):
  if len(num_l)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if num_l[b]-num_l[a]==c:
        t_ans+=d
    ans=max(t_ans,ans)
    return

  for i in range(num_l[-1],m+1):
    dfs(num_l+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

print(ans)

Submission status: Accepted

Solution code:
import itertools


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

a = []
b = []
c = []
d = []

for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

A_pattern = []

# N = 4, M = 6
def dfs(A): # Aは配列 [1, 1, 2, 2]
    if (len(A) == N):
        A_pattern.append(A.copy())
        return
    else:
        for i in range(A[-1], M+1):
            A.append(i)
            dfs(A)
            A.pop(-1)

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


"""
A = [i for i in range(1, M+1)] # [1, 2, 3, 4, ... M]
A_pattern = list(itertools.combinations_with_replacement(A, N)) # Aの配列の中から重複してもいいのでN個選ぶ
"""

ans = 0

for a_pattern in A_pattern: # 数列全部調べる
    ansi = 0
    for i in range(Q): # 得点になるかどうか調べる
        if a_pattern[b[i]-1] - a_pattern[a[i]-1] == c[i]: # A[bi] - A[ai] == ci -> ansi += di
            ansi += d[i]

    ans = max(ans, ansi)

print(ans)

Submission status: Accepted

Solution code:
import itertools


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

a = []
b = []
c = []
d = []

for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

A = [i for i in range(1, M+1)] # [1, 2, 3, 4, ... M]

A_pattern = list(itertools.combinations_with_replacement(A, N))

ans = 0

for a_pattern in A_pattern: # 数列全部調べる
    ansi = 0
    for i in range(Q): # 得点になるかどうか調べる
        if a_pattern[b[i]-1] - a_pattern[a[i]-1] == c[i]: # A[bi] - A[ai] == ci -> ansi += di
            ansi += d[i]

    ans = max(ans, ansi)


print(ans)

Submission status: Accepted

Solution code:
import itertools as ite

n,m,q = map(int,input().split())
a,b,c,d = [],[],[],[]
for i in range(q):
    aa,bb,cc,dd = map(int,input().split())
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

# subscritableとかcollableのとき、すでに使ってる変数に注意！
combs = ite.combinations_with_replacement([i for i in range(1,m+1)], n)
scores = []
for arr in combs:
    arr = list(arr)
    score = 0
    for i in range(q):
        aa,bb,cc,dd = a[i]-1,b[i]-1,c[i],d[i]
        if arr[bb]-arr[aa] == cc : score += dd
    scores.append(score)

ans = max(scores)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n,m,q = list(map(int, input().split()))
abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))
abcd = np.array(abcd)
P = np.array(list(itertools.combinations_with_replacement(range(1,m+1),n)))

max_s = 0
for i in P:
    target = (i[abcd[:,1]-1] - i[abcd[:,0]-1] == abcd[:,2])
    val = np.sum(abcd[target,3])
    if max_s < val : max_s = val

print(max_s)

Submission status: Accepted

Solution code:
def cwrlp(data,r):
	if r <= 0:
		return []
	
	result = []
	_cwrlp(data, r, 0, [], result)
	return result

def _cwrlp(data, r, start, progress, result):
	if r == 0:
		result.append(progress)
		return
	
	for i in range(start, len(data)):
		_cwrlp(data, r-1, i, progress + [data[i]], result)

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

#dataset = cwrlp(range(1,m+1),n)

#print(dataset)
ret = 0
for da in cwrlp(range(1,m+1),n):
#	print(da)
	ans = 0
	for i in range(q):
		a = abcd[i][0]
		b = abcd[i][1]
		c = abcd[i][2]
		if(da[b-1]-da[a-1] == c):
			d = abcd[i][3]
			ans += d
#			print(a,b,c,d,ans)
	ret = max(ret,ans)
print(ret)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
L = []
for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    ai -= 1
    bi -= 1
    L.append((ai, bi, ci, di))

ans = 0
for A in combinations_with_replacement(range(M), N):
    r = 0
    for Li in L:
        if A[Li[1]] - A[Li[0]] == Li[2]:
            r += Li[3]
    ans = max(ans, r)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(Q)]
com = list(itertools.combinations_with_replacement(range(1,M+1),N))
answer = 0
for i in com:
    ans = 0
    for j in A:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            ans += j[3]
    answer = max(answer,ans)
print(answer)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
import numpy as np

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

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

ans = 0

# 可能な数列Aの全探索、そのままやとめちゃ多いからなんか工夫する？
# そもそもAの全探索方がいまいちわからん...

A = np.array(list(combinations_with_replacement(range(1, M + 1), N)))
scores = np.zeros(len(A), dtype=np.int32)
for g in G:
    a, b, c, d = g
    cond = A[:, b - 1] - A[:, a - 1] == c
    scores += d * cond

print(scores.max())

Submission status: Accepted

Solution code:
import itertools

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    query = []
    for i in range(q):
        a, b, c, d = map(int, input().split())
        query.append((a - 1, b - 1, c, d))

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

    print(ans)

Submission status: Accepted

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

a = [0] * 55; b = [0] * 55; c = [0] * 55; d = [0] * 55

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

def socer(A):
    now = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]: now += d[i]
    return now

def dfs(A):
    # print(A)
    if len(A) == n: return socer(A)
    res = 0
    last = A[-1] if A else 0
    for i in range(last, m):
        A.append(i)
        res = max(res, dfs(A))
        A.pop()
    return res
      
print(dfs([]))

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
a=[0]*Q
b=[0]*Q
c=[0]*Q
d=[0]*Q
for i in range(Q):
  a[i],b[i],c[i],d[i]=map(int,input().split())
import itertools
ans=0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
    A=list(A)
    s=0
    
    for i in range(Q):
        if A[b[i]-1]-A[a[i]-1]==c[i]:
           s+=d[i]

           ans=max(ans,s)
print(ans)

Submission status: Accepted

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


def dfs(A):
    if len(A)==N:
        return calc(A)
    
    res = 0
    s = A[-1] if len(A)>0 else 1
    for i in range(s, M+1):
        A.append(i)
        res = max(res, dfs(A))
        A.pop()
    return res
        
    
def calc(A):
    score = 0
    for a,b,c,d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    return score


ans = dfs([])
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []
for _ in range(Q):
    abcd = list(map(int, input().split()))
    a.append(abcd[0]-1)
    b.append(abcd[1]-1)
    c.append(abcd[2])
    d.append(abcd[3])

import itertools
ans = 0
for p in itertools.combinations_with_replacement([i for i in range(1, M+1)], N):
    tmp_ans = 0
    for i in range(Q):
        if p[b[i]] - p[a[i]] == c[i]:
            tmp_ans += d[i]
    if tmp_ans > ans:
        ans = tmp_ans
print(ans)

Submission status: Accepted

Solution code:
n, m, q = map(int,input().split())
a, b, c, d = [0] * q,[0] * q, [0] * q, [0] * q

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

def score(z):
    tmp = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if z[bi] - z[ai] == ci:
            tmp += di
    return tmp

def dfs(a):
    if len(a) == n:
        return score(a)
    ans = 0
    prev_last = a[-1] if len(a) > 0 else 0
    for v in range(prev_last,m):
        a.append(v)
        ans = max(ans,dfs(a))
        a.pop()
    return ans

print(dfs([]))

Submission status: Accepted

Solution code:
def main():
    N, M, Q = list(map(int, input().split()))
    ABCD = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        ABCD.append((a - 1, b - 1, c, d))
    ABCD.sort()
    A = [-1] * N

    def helper(n, m):
        if n == N:
            return sum(d for a, b, c, d in ABCD if A[b] - A[a] == c)
        t = 0
        for i in range(m, M + 1):
            A[n] = i
            t = max(t, helper(n + 1, i))
        return t

    return helper(0, 1)
        

print(main())

Submission status: Accepted

Solution code:
#damedatta...
import itertools
def main():
    N, M, Q = map(int, input().split())
    l = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())       
        a -= 1
        b -= 1
        l.append((a,b,c,d))
    r = 0
    for i in itertools.combinations_with_replacement([i for i in range(1, M+1)],N):
        t = 0
        for j in l:
            a,b,c,d = j
            if i[b] - i[a] == c:
                t += d
        r = max(r, t)
    return r
print(main())

Submission status: Accepted

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

def score(A):
    tmp = 0
    for a, b, c, d in abcd:
        if A[b] - A[a] == c:
            tmp += d
    return tmp
    
def dfs(A):
    if len(A) == n: return score(A)
    res = 0
    last = A[-1] if A else 0
    for i in range(last, m):
        A.append(i)
        res = max(res, dfs(A))
        A.pop()
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
import itertools

n,m,q = map(int,input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

mm = [0]*m

for k in range(1,m+1,1):
    mm[k-1]=k

A = list(itertools.combinations_with_replacement(mm, n))
su = 0
ans = 0

for x in range(len(A)):
    l=A[x]
    su = 0
    for h in range(q):
        if l[b[h]-1]-l[a[h]-1] == c[h]:
            su += d[h]

    if su > ans:
        ans = su

print(str(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import combinations


def gen_step(s, n):
    # 和がsとなるn個の非負整数列
    # a1 + a2 + ... + an = s
    if n == 0:
        yield []
        return
    if n == 1:
        yield [s]
        return
    for i in range(s + 1):
        for step in gen_step(s - i, n - 1):
            yield [i] + step


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    ans = 0
    for s in range(M):
        for steps in gen_step(s, N - 1):
            ret = 0
            A = [1] * N
            for i, step in enumerate(steps):
                A[i + 1] = A[i] + step
            for q in range(Q):
                if A[b[q] - 1] - A[a[q] - 1] == c[q]:
                    ret += d[q]
            ans = max(ans, ret)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(q):
    if len(q) == N:
        sum = 0
        for a,b,c,d in query:
            if q[b]-q[a] == c:
                sum+=d
        return sum
    
    if len(q) > 0:
        last = q[-1]
    else:
        last = 1

    ans = 0
    for i in range(last, M+1):
        q.append(i)
        ans = max(ans,dfs(q))
        q.pop()
    return ans

print(dfs([]))

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations_with_replacement
    n, m, q = map(int, input().split())
    requirements = [list(map(int, input().split())) for _ in range(q)]

    score_max = 0
    for a in combinations_with_replacement(range(1, m+1), n):
        score = 0
        for requirement in requirements:
            if a[requirement[1]-1] - a[requirement[0]-1] == requirement[2]:
                score += requirement[3]
        score_max = max(score, score_max)

    print(score_max)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a=[]
b=[]
c=[]
d=[]

max_= 0

def dfs(A):
  global max_
  ans = 0
  last = A[-1]
  if len(A) == n+1:
    for i in range(q):
      if A[b[i]]-A[a[i]] == c[i]:
        ans += d[i]
    max_ = max(max_, ans)
    return
  for i in range(last, m+1):
    dfs(A+[i])  


for i in range(q):
  aa,bb,cc,dd = map(int, input().split())
  a.append(aa)
  b.append(bb)
  c.append(cc)
  d.append(dd)
  
dfs([1])

print(max_)

Submission status: Accepted

Solution code:
import itertools
import math

def dfs(vum,v,depth,max_depth,candidate,dupcombi):
    if depth == max_depth:
        dupcombi.append(candidate.copy())
    else:
        for u in vum[v]:
            candidate[depth] = u
            candidate, dupcombi = dfs(vum,u,depth+1,max_depth,candidate,dupcombi)
    return candidate, dupcombi

def main():
    N,M,Q = [int(x) for x in input().split()]
    m = []
    for i in range(Q):
        a,b,c,d = [int(x) for x in input().split()]
        m.append((a,b,c,d))

    # 数列列挙
    vum = {}
    for i in range(1,M+1):
        ul = []
        for j in range(i,M+1):
            ul.append(j)
        vum.update({i:ul})
    dupcombi = []
    candidate = [0]*N
    _, candA = dfs(vum,1,0,N,candidate,dupcombi)
    # print(len(list(itertools.product(range(1,M+1),repeat=N)))) // 重複あり順列
    # print(len(list(itertools.combinations_with_replacement(range(1,M+1),N)))) // 重複あり組み合わせ
    # print(len(candA)) // 重複あり組み合わせ (自作)

    scoreA = {}
    for cand in candA:
        score = 0
        for a,b,c,d in m:
            # print(a,b,c,d)
            if cand[b-1] - cand[a-1] == c:
                # print(cand[b-1],cand[a-1])
                score += d
        # print(cand,score)
        scoreA.update({score:cand})
    print(sorted(scoreA.items(), reverse=True)[0][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def dfs(nl):
  if len(nl)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if nl[b]-nl[a]==c:
        t_ans+=d
    ans=max(ans,t_ans)
    return

  for i in range(nl[-1], m+1):
        dfs(nl+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc165/tasks/abc165_c
# C - Many Requirements
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    # 数列Aのスコアを返す
    def calc_score(L):
        score = 0
        for a, b, c, d in ABCD:
            if L[b - 1] - L[a - 1] == c:
                score += d
        return score

    # 数列Aを全パターン試す
    def dfs(A):
        if len(A) == n:
            return calc_score(A)

        res = 0
        prev = A[-1] if len(A) > 0 else 1
        for v in range(prev, m + 1):
            A.append(v)
            res = max(res, dfs(A))
            A.pop()

        return res

    print(dfs([]))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import itertools

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

C = list(itertools.combinations_with_replacement([i+1 for i in range(m)], n))

ans = 0

for c in C:
    tmp = 0
    for p in P:
        if c[p[1]-1] - c[p[0]-1] == p[2]:
            tmp += p[3]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
S = list(combinations_with_replacement(range(1, m + 1), n))

ans = 0
for s in S:
    cnt = 0
    for a, b, c, d in abcd:
        if s[b - 1] - s[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

alist = []


def bfs(depth: int, l: list):
    global n, m, alist
    if depth == n:
        alist.append(l[1:])
        return
    c = l[depth]
    cl = l.copy()
    cl.append(c)
    bfs(depth+1, cl)
    while c < m:
        c += 1
        cl = l.copy()
        cl.append(c)
        bfs(depth + 1, cl)


bfs(0, [1])
pmax = 0
for a in alist:
    point = 0
    for p in plist:
        if (a[p[1]-1] - a[p[0]-1] == p[2]):
            point += p[3]
    pmax = max(pmax, point)

print(pmax)

Submission status: Accepted

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

alist = []


def bfs(depth: int, l: list):
    global n, m, alist
    if depth == n:
        alist.append(l[1:])
        return
    c = l[depth]
    cl = l.copy()
    cl.append(c)
    bfs(depth+1, cl.copy())
    while c < m:
        c += 1
        cl = l.copy()
        cl.append(c)
        bfs(depth + 1, cl.copy())


bfs(0, [1])
pmax = 0
for a in alist:
    point = 0
    for p in plist:
        if (a[p[1]-1] - a[p[0]-1] == p[2]):
            point += p[3]
    pmax = max(pmax, point)

print(pmax)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    cnt = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            cnt += d[i]
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
A = [0]*n
ans = 0
def dfs(h):
    global ans
    if h == n-1:
        cnt = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                cnt += d[i]
        ans = max(ans,cnt)
    else:
        for i in range(A[h],m+1):
            A[h+1] = i
            dfs(h+1)
    return

for i in range(1,m+1):
    A[0] = i
    dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q = map(int, input().split())
abcd = []
for _ in range(q):
  a,b,c,d = map(int, input().split())
  abcd.append([a,b,c,d])

nums = list(range(1,m+1))
l = list(combinations_with_replacement(nums, n))

ans = 0
for i in l:
  p = 0
  for j in abcd:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      p += j[3]
  ans = max(ans, p)
  
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q = map(int, input().split())
abcd = []
for _ in range(q):
  a,b,c,d = map(int, input().split())
  abcd.append([a,b,c,d])

nums = list(range(1,m+1))
l = list(combinations_with_replacement(nums, n))

ans = 0
for i in l:
  p = 0
  for j in abcd:
    b = i[j[1]-1]
    a = i[j[0]-1]
    if b - a == j[2]:
      p += j[3]
  ans = max(ans, p)
  
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q=list(map(int,input().split()))
src=[]
for q in range(Q):
  src.append(list(map(int,input().split())))
ML=[n+1 for n in range(M)]
X=list(itertools.combinations_with_replacement(ML,N))
L=[]
for x in X:
  a=0
  for s in src:
    if x[s[1]-1] - x[s[0]-1] == s[2]:
      a+=s[3]
  L.append(a)
print(max(L))

Submission status: Accepted

Solution code:
from collections import deque
n, m, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

# a = itertools.combinations_with_replacement(range(1, m + 1), n)
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC

def dfs():
  stack = deque()
  for i in range(1, m + 1):
    stack.append([i])
  while stack:
    q = stack.popleft()
    if len(q) >= n:
      a.append(q)
    else:
      l = q[-1]
      for i in range(l, m + 1):
        stack.append(q + [i])

a = []
dfs()

ans = 0
for i in a:
  prs = 0
  for a, b, c, d in ABCD:
    if i[b - 1] - i[a - 1] == c:
      prs += d
  ans = max(ans, prs) 

print(ans)