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:
from itertools import combinations_with_replacement

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

A=list(combinations_with_replacement(range(1,m+1),n))

res=0

for i in range(len(A)):
    tmp=0
    for j in range(len(l)):
        if A[i][l[j][1]-1]-A[i][l[j][0]-1]==l[j][2]:
            tmp+=l[j][3]

    res=max(res, tmp)

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
from sys import stdin
input = stdin.readline

N,M,Q = map(int, input().split())
L = [None for _ in range(Q)]
A = [0]*M
for q in range(Q):
    a,b,c,d = map(int, input().split())
    L[q] = [a,b,c,d]
maxtotal = 0
for tup in combinations_with_replacement(list(range(1,M+1)),N):
    total = 0
    for lis in L:
        total += lis[3] if tup[lis[1]-1] - tup[lis[0]-1] == lis[2] else 0
    maxtotal = max(maxtotal, total)
print(maxtotal)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

A=list(combinations_with_replacement(range(1,m+1),n))

res=0

for i in range(len(A)):
    tmp=0
    for j in range(len(l)):
        if A[i][l[j][1]-1]-A[i][l[j][0]-1]==l[j][2]:
            tmp+=l[j][3]

    res=max(res, tmp)

print(res)

Submission status: Accepted

Solution code:
import itertools

N,M,Q=map(int, input().split())
abcd=[list(map(int, input().split())) for _ in range(Q)]
ans=0
for c in itertools.combinations_with_replacement(range(M),N):
	tmp=0
	for i in range(Q):
		if c[abcd[i][1]-1]-c[abcd[i][0]-1]==abcd[i][2]:
			tmp+=abcd[i][3]
	ans=max(ans, tmp)
print(ans)

Submission status: Accepted

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

max_points = 0
def dfs(ary):
    global max_points

    if len(ary) == n:
        points = 0
        for c in conditions:
            if ary[c[1] - 1] - ary[c[0] - 1] == c[2]:
                points += c[3]
        max_points = max(max_points, points)
        return
    
    if len(ary) == 0:
        minimum = 1
    else:
        minimum = ary[-1]

    for i in range(minimum, m+1):
        ary.append(i)
        dfs(ary)
        ary.pop(-1)

dfs([])
print(max_points)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

selections = combinations_with_replacement(range(1, m+1), n)

maximum_points = 0
for s in selections:
    for i in range(n-1):
        if s[i] > s[i+1]:
            continue
    points = 0
    for c in conditions:
        if s[c[1]-1] - s[c[0]-1] == c[2]:
            points += c[3]
    maximum_points = max(maximum_points, points)
print(maximum_points)

Submission status: Accepted

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

A = []
for i in range(1, M + 1):
    A.append(i)
H = list(itertools.combinations_with_replacement(A, N))

C = 0
while len(H) > 0:
    CC = 0
    h = H.pop()
    for i in range(Q):
        a = abcd[i][0] - 1
        b = abcd[i][1] - 1
        c = abcd[i][2]
        d = abcd[i][3]
        if h[b] - h[a] == c:
            CC += d
    C = max(C, CC)
print(C)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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


arr = [0]*(n+m)
for j in range(m):
    arr[j] = 1

ans = 0

for A in combinations_with_replacement(range(1,m+1),n):
    score = 0
    for l in range(q):
        if A[b[l]] - A[a[l]] == c[l]:
            score += d[l]

    ans = max(ans,score)

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    li = [i for i in range(1, m + 1)]
    max_point = 0
    for a in combinations_with_replacement(li, n):
        point = 0
        for qer in query:
            if a[qer[1] - 1] - a[qer[0] - 1] == qer[2]:
                point += qer[3]
        if point > max_point:
            max_point = point
    print(max_point)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    li = [0] * m
    for i in range(1, m + 1):
        li[i - 1] = i
    max_point = 0
    for a in combinations_with_replacement(li, n):
        point = 0
        for qer in query:
            if a[qer[1] - 1] - a[qer[0] - 1] == qer[2]:
                point += qer[3]
        if point > max_point:
            max_point = point
    print(max_point)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product
N,M,Q=map(int,input().split())
a=[i for i in range(1,M+1)]
A=list(combinations_with_replacement(a,N))
B=[list(map(int,input().split())) for i in range(Q)]
ans=[]
for i in A:
    tmp=0
    #print(i)
    for j in B:
        #print(j)
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            tmp+=j[3]
        else:
            pass
    ans.append(tmp)
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    N, M, Q = map(int, input().split())
    combination = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        combination.append((a, b, c, d))
    ans = []
    for p in combinations_with_replacement(list(range(1, M+1)), N):
        cnt = 0
        for a, b, c, d in combination:
            if p[b] - p[a] == c:
                cnt += d
        ans.append(cnt)

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import itertools

# タグ、順列、組み合わせ

# abcd・・a=<b=<=<d・・という塊は、広義単調増加等と言うらしい。
#     参考：単調増加等の説明：https://mathtrain.jp/tantyou
# そして、この組み合わせを網羅するには、重複組合せを使える。
#     参考：重複組合せ：https://mathtrain.jp/tyohukuc
# 最大の組み合わせ数は20C10になる、と思ったが、違う。20C10が正しいらしい。
# 実装方法はこんな感じ。
#     https://qiita.com/junkls/items/10384950963056cc8e08
# 問題文の意味が分かりずらい・・15分かかった。
# 例)
# ---入力例---
#   3 4 3
#   1 3 3 100
#   1 2 2 10
#   2 3 2 10

#   1 3 3 100の場合・・
#   「3番目の数字 - 1番目の数字 = 3になる場合100点加算。」という意味。

# ---出力---
#   110
#   ->A[1, 3, 4]の時・・
#     「1 3 3 100」->A[3](つまり4) - A[1](つまり1) = 3 だから100点加算。
#     「1 2 2  10」->A[2](つまり3) - A[1](つまり1) = 2 だから 10点加算。
#     「2 3 2  10」->A[3](つまり4) - A[2](つまり3) = 1(=2じゃない) だから 加算なし。

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

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

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

    point = 0
    for target in targets:
        work_point = 0
        for num in num_list:
            # 条件を満たすならポイント加算。
            # ※targetsは0始まりの配列、num_listは1始まるの値が格納されているので、targetの添え字を指定するとき-1している。
            if target[num[1]-1] - target[num[0]-1] == num[2]:
                work_point += num[3]

        # 最適解を格納
        point = max(point, work_point)

    print(point)




class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,m,q=INTM()
    aq=[]
    for i in range(q):
        aq.append(LIST())
    number = [int(i+1) for i in range(m)]
    
    ans=0
    for i in combinations_with_replacement(number,n):
        temp=0
        for k in aq:
            if i[k[1]-1]-i[k[0]-1]==k[2]:
                temp+=k[3]
        ans=max(ans,temp)
    print(ans)
    
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcds = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  abcds.append((a-1, b-1, c, d))
rs = []
for B in itertools.combinations(range(M+N-1), N):
  #print(B)
  A = [0]
  n = 0
  for b in B:
    a = A[-1]+b-n
    A.append(a)
    n = b+1
  A.pop(0)
  r = 0
  for a, b, c, d in abcds:
    if A[b]-A[a] == c:
      r += d
  #print(B, A, r)
  rs.append(r)
r = max(rs)
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def main():
    n, m, q = [int(i) for i in input().split()]
    arr = []
    for _ in range(q):
        arr.append([int(i) for i in input().split()])
    base = [int(i+1) for i in range(m)]

    max_score = 0
    for comb in combinations_with_replacement(base, n):
        score = 0
        for ar in arr:
            a, b, c, d = ar
            if comb[b-1] - comb[a-1] == c:
                score += d
        max_score = max(max_score, score)
    print(max_score)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int, input().split())
candidates = [i for i in range(1,m+1)]
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())

max_score = 0
for A in itertools.combinations_with_replacement(candidates, n):
  A = list(A)
  score = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      score += d[i]
  max_score = max(max_score, score)
print(max_score)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
# n個の数列、1~mの中で数列を作る
# 2<=n<=10
# 1<=m<=10
n, m, q = map(int, input().split())

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

ans = 0
for A in comb:
    cnt = 0
    for a,b,c,d in abcd:
        if A[b - 1] - A[a - 1] == c:
            cnt += d
    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

ans = 0

for i in range(Q):
    ai,bi,ci,di = map(int,input().split())
    # ai,biは添字
    a[i] = ai -1
    b[i] = bi -1
    c[i] = ci
    d[i] = di

#全探索DFS
def dfs(A):
    if len(A) == N:
        score = 0
        for i in range(Q):
            if (A[b[i]] - A[a[i]] ) == c[i]:
                score += d[i]
        global ans
        ans = max(ans,score)
        return
    #数列の最後の値を確認する
    #数列の長さが 0 のときは1
    prev_last = A[-1] if len(A) > 0 else 1

    #1<A1<A2 ..... < An の単調増加なので
    #vを回す範囲は数列の前回の値の最後の値から
    for v in range(prev_last,M+1):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n,m,q =map(int,input().split())
A,B,C,D=[],[],[],[]
res=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    D.append(d)
    
for p in combinations_with_replacement(list(range(1,m+1)),n):
    cnt=0
    for a,b,c,d in zip(A,B,C,D):
            if p[b] - p[a] ==c:
                cnt+=d
    res.append(cnt)
    
print(max(res))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n,m,q =map(int,input().split())
summa=[]
res=[]
for i in range(q):
    a=[int(i) for i in input().split()]
    summa.append(a)
    
for i in combinations_with_replacement(list(range(1,m+1)),n):
    cnt=0
    for j in summa:
            if i[j[1]-1]-i[j[0]-1]==j[2]:
                cnt += j[3]
            
    res.append(cnt)
    
print(max(res))

Submission status: Accepted

Solution code:
def dfs(n, lower):
    if n == N:
        return [[]]
    else:
        res = []
        for i in range(lower, M + 1):
            for p in dfs(n + 1, i):
                res.append([i] + p)
        return res


N, M, Q = map(int, input().split())
A, B, C, D = [], [], [], []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    C.append(c)
    D.append(d)
res = 0
for p in dfs(0, 1):
    cur = 0
    for a, b, c, d in zip(A, B, C, D):
        if p[b] - p[a] == c:
            cur += d
    res = max(res, cur)
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
A, B, C, D = [], [], [], []
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a - 1)
    B.append(b - 1)
    C.append(c)
    D.append(d)
res = 0
for p in combinations_with_replacement(list(range(1, M + 1)), N):
    cur = 0
    for a, b, c, d in zip(A, B, C, D):
        if p[b] - p[a] == c:
            cur += d
    res = max(res, cur)
print(res)

Submission status: Accepted

Solution code:
import copy
N, M, Q = map(int, input().split())
Qj = [list(map(int, input().split())) for i in range(Q)]

ans = 0

def dfs(Aj):
	global ans
	if len(Aj) == N:
		now = 0
		for Q in Qj:
			if Aj[Q[1]-1] - Aj[Q[0]-1] == Q[2]:
				now += Q[3]
		ans = max(ans, now)
		return;
	if len(Aj) == 0:
		Aj.append(1)
	else:
		Aj.append(Aj[-1])
	while Aj[-1] <= M:
		dfs(copy.deepcopy(Aj))
		Aj[-1] += 1
Aj = []
dfs(Aj)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

def calc(arr):
    score = 0
    for a, b, c, d in X:
        if arr[b - 1] - arr[a - 1] == c:
            score += d
    return score


def dfs(arr):
    global ans
    if len(arr) == N:
        ans = max(ans, calc(arr))

    elif len(arr) == 0:
        for nx in range(1, M + 1):
            dfs(arr + [nx])

    else:
        for nx in range(arr[-1], M + 1):
            dfs(arr + [nx])


dfs([])
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(maxsize=None)
def search(n, l, m):
    if n == 0:
        return [[]]
    ret = []
    for i in range(l, m+1):
        for v in search(n-1, i, m):
            ret.append([i] + v)
    return ret


def main():
    n, m, q = [int(v) for v in input().split()]
    val = [[int(v) for v in input().split()] for _ in range(q)]
    ans = 0
    for arr in search(n, 1, m):
        score = 0
        for i in range(q):
            a, b, c, d = val[i]
            if arr[b-1] - arr[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def amp(seqs):
    for seq in seqs:
        s = seq[-1]
        for i in range(s, m+1):
            yield seq + [i]

seed = [[i+1] for i in range(m)]
seq = seed
for _ in range(n-1):
    seq = amp(seq)

all_an = list(seq)
dn = max(sum(d for a,b,c,d in pairs if an[b-1] - an[a-1] == c) for an in all_an)
print(dn)

Submission status: Accepted

Solution code:
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

import copy

n,m,q = i2()
a = []
b = []
c = []
d = []

for i in range(q):
	ai,bi,ci,di = i2()
	a.append(ai)
	b.append(bi)
	c.append(ci)
	d.append(di)
#print(n,m,q)
#print(a,b,c,d)

l = [1]
ans = []
def saiki(l):
	if len(l) == n+1:
		sum = 0
		for j in range(q):
			#print(j)
			#print(l)
			if l[b[j]] - l[a[j]] == c[j]:
				sum += d[j]
		ans.append(sum)
		return
	l.append(l[-1])
	while l[-1] <= m:
		saiki(copy.copy(l))
		l[-1] += 1
saiki(l)
print(max(ans))

Submission status: Accepted

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

As = [[i] for i in range(1, m+1)]

while len(As[0]) != n:
    current = As.pop(0)
    for i in range(current[-1], m+1):
        As.append(current+[i])

inputs = []

for _ in range(q):
    inputs.append(list(map(int, input().split())))

answer = 0

for A in As:
    local_ans = 0
    for i in inputs:
        if A[i[1]-1]-A[i[0]-1] == i[2]:
            local_ans += i[3]
    answer = max(answer, local_ans)

print(answer)

Submission status: Accepted

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

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

for _ in range(q):
    ins = list(map(int, input().split()))
    a.append(ins[0])
    b.append(ins[1])
    c.append(ins[2])
    d.append(ins[3])
 
A = [[i] for i in range(1, m+1)]
 
while len(A[0]) != n:
    current = A.pop(0)
    for i in range(current[-1], m+1):
        A.append(current+[i])
 
maxima = 0
for item in A:
    accumulate = 0
    for i in range(q):
        if (item[b[i]-1] - item[a[i]-1]) == c[i]:
            accumulate += d[i]
    if accumulate > maxima:
        maxima = accumulate

print(maxima)

Submission status: Accepted

Solution code:
import itertools

length, max_num, comb_num = map(int, input().split())
targets = [list(map(int, input().split())) for i in range(comb_num)]

combs = list(itertools.combinations_with_replacement(
    range(1, max_num+1), length))

result = 0
for comb in combs:
    total = 0
    for a, b, c, d in targets:
        a -= 1
        b -= 1
        if comb[b] - comb[a] == c:
            total += d
    if result < total:
        result = total

print(result)

Submission status: Accepted

Solution code:
def score(A,g):
    score = 0
    for p in g:
        if A[p[1]]-A[p[0]]==p[2]:
            score+=p[3]
    return score

def solve(m,n,g,A,dep):
    if dep==n:
        return score(A,g)
    else:
        temp_scores = []
        for i in range(A[dep],m+1):
            A[dep+1] = i
            temp_scores.append(solve(m,n,g,A,dep+1))
        return max(temp_scores)

def main():
    n,m,q = map(int,input().split())
    g = []
    for _ in range(q):
        a,b,c,d = map(int,input().split())
        g.append((a,b,c,d))
    A = [0]*(n+1)
    A[0]=1
    print(solve(m,n,g,A,0))
main()

Submission status: Accepted

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

def f(A):
    res = 0
    for i in range(Q):
        if A[L[i][1]-1]-A[L[i][0]-1] == L[i][2]:
            res += L[i][3]

    return res

import itertools

nums = [i for i in range(1, M+1)]
ans = 0
for A in itertools.combinations_with_replacement(nums, N):
    ans = max(ans, f(A))

print(ans)

Submission status: Accepted

Solution code:
#C
import itertools

def point(abcd,lst):
    p = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] - lst[a-1] == c:
            p += d
    return p

N,M,Q = map(int,input().split())
check = [None]*Q
for i in range(Q):
    check[i] = list(map(int,input().split()))

#print(check)
#print(check[1])

nums = list(range(1,M+1))
ans = 0

for comb in itertools.combinations_with_replacement(nums, N):
    #print(sorted(comb))
    ans = max(point(check,sorted(comb)),ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    combs = combinations_with_replacement(range(1, M + 1), N)
    ans = 0
    for A in combs:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                tmp += d

        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
input_lists = []
A = []
point = [0]

for _ in range(Q):
    input_lists.append([int(i) for i in input().split()])

for A in itertools.combinations_with_replacement(range(1, M+1), N):
    d_sum = 0
    for input_list in input_lists:
        a, b, c, d = input_list
        if A[b-1] - A[a-1] == c:
            d_sum += d
    point.append(d_sum)

print(max(point))

Submission status: Accepted

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


def dfs(li):
    if len(li) >= n:
        s = sum(d[i] for i in range(q) if li[b[i]] - li[a[i]] == c[i])
        return s
    res = 0
    for i in range(li[-1], m + 1):
        res = max(res, dfs(li + [i]))
    return res


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

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

Submission status: Accepted

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

array = []
for i in range(q):
    a = list(map(int, input().split()))
    array.append(a)

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

ans = 0
for i in comb:
    score = 0
    for a, b, c, d in array:
        if i[b-1] - i[a-1] == c:
            score += d
        ans = max(ans, score)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
for A in combinations_with_replacement(range(1, m+1), n):
    point = 0
    for a, b, c, d in query:
        if A[b-1] - A[a-1] == c:
            point += d
    ans = max(point, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

from collections import deque



def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b - 1] - seq[a - 1] == c:
            score += d

    return score


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

ans = 0

que = deque()


for i in range(1, m + 1):
    que.append([i])

while que:
    seq = que.popleft()

    if len(seq) == n:
        
        score = calc(seq)
        ans = max(ans, score)
    else:
        
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

from itertools import combinations_with_replacement as cwr
n,m,q=mp()
l=[lmp() for i in range(q)]
ans=0


for i in cwr(range(1,m+1),n):
    s=0
    for a,b,c,d in l:
        if i[b-1]-i[a-1]==c:
            s+=d
    ans=max(ans,s)
print(ans)

Submission status: Accepted

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

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

score = 0

a = [1] * n

def sco(a):
    scotem = 0
    for i in sets:
        if(a[i[1]-1] - a[i[0]-1] == i[2]):
            scotem += i[3]
    return scotem

flag = 1

while True:
    for i in range(n-1,-1,-1):
        flag = 0
        if(a[i] < m):
            flag = 1
            a[i] = a[i] + 1
            for j in range(n-1,i,-1):
                a[j] = a[i]
            if(sco(a) > score):
                score = sco(a)
            break
    if (flag == False):
        if(sco(a) > score):
            score = sco(a)
        break

print(str(score))

Submission status: Accepted

Solution code:
# 解説を参考に作成


def solve():
    N, M, Q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(Q)]

    # AAs first is minmum M.
    def dfs(AA=[1], now_max=0):
        A = AA.copy()
        if len(A) == N + 1:
            new_max = 0
            for a, b, c, d in abcd:
                if A[b] - A[a] == c:
                    new_max += d
            now_max = max(now_max, new_max)
        else:
            for i in range(A[-1], M + 1):
                now_max = max(now_max, dfs(A + [i], now_max))
        return now_max

    print(dfs())


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
ABCD = [tuple(map(int,input().split())) for i in range(Q)]
import itertools
ans = 0
for ptn in itertools.combinations_with_replacement(range(1,M+1), N):
    tmp = 0
    for a,b,c,d in ABCD:
        if ptn[b-1] - ptn[a-1] == c:
            tmp += d
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

def calc(arr):
    score = 0
    for a, b, c, d in X:
        if arr[b - 1] - arr[a - 1] == c:
            score += d
    return score


def dfs(arr):
    global ans
    if len(arr) == N:
        ans = max(ans, calc(arr))

    elif len(arr) == 0:
        for nx in range(1, M + 1):
            dfs(arr + [nx])

    else:
        for nx in range(arr[-1], M + 1):
            dfs(arr + [nx])


dfs([])
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    tmp_ans = 0
    pattern = list(pattern)
    for a, b, c, d in X:
        if pattern[b - 1] - pattern[a - 1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-05-20 00:27:08 +0900
# LastModified: 2020-05-20 13:11:16 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd
from itertools import combinations_with_replacement as crlp

def main():
    n,m,q = map(int,input().split())
    ans = 0
    a = []
    b = []
    c = []
    d = []
    for _ in range(q):
        a_,b_,c_,d_ = map(int,input().split())
        a.append(a_-1)
        b.append(b_-1)
        c.append(c_)
        d.append(d_)

    for seq in crlp(range(1,m+1),n):
        tmp = 0
#        print(seq)
        for i in range(q):
            if seq[b[i]]-seq[a[i]]==c[i]:
                tmp+=d[i]
        if ans<tmp:
            ans=tmp
    print(ans)

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

n,m,q = map(int, input().split(" "))
a,b,c,d = [],[],[],[]
for i in range(q):
  inpu = input()
  a.append((int)(inpu.split(" ")[0]))
  b.append((int)(inpu.split(" ")[1]))
  c.append((int)(inpu.split(" ")[2]))
  d.append((int)(inpu.split(" ")[3]))

balls = list(itertools.combinations_with_replacement(range(1, m + 1), n))
#print(balls)
max = 0
for i in range(len(balls)):
  temp = 0
  for j in range(q):
    if balls[i][b[j] - 1] - balls[i][a[j] - 1] == c[j]:
      temp += d[j]
  if temp > max:
    max = temp
print(max)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M, Q = LI()
numlist = [LI() for _ in range(Q)]
part = 0
sum = 0
maxAs = 0
hist = []
stack = collections.deque()
stack.append([1,-1])	#sumleft, histpos
while True:
	now = stack.pop()
	sumleft = now[0]
	histpos = now[1]
	hist.append(sumleft)
	histpos+=1
	if histpos == N:
		# 計算してもとに戻る
		val = 0
		for l in numlist:
			if hist[l[1]-1]-hist[l[0]-1] == l[2]:
				val+=l[3]
		if val > maxAs:
			maxAs = val
		if not stack:
			break
		next = stack[len(stack)-1]
		hist = hist[0:next[1]+1]
		continue
	for i in range(0,M+1-sumleft):
		stack.append([sumleft+i, histpos])
print(maxAs)

Submission status: Accepted

Solution code:
def nex(x,m):
    for c in range(len(x)-1,-1,-1):
        if x[c]<m:
            x[c]+=1
            for d in range(c+1,len(x)):
                x[d]=x[c]
            return x
    return -1


n,m,q=map(int,input().split())
f=[]
for i in range(q):
    f.append([int(x) for x in input().split()])

s=0
a=[1]*n
while True:
    if a==-1:
        break
    p=0
    for i in range(q):
        if a[f[i][1]-1]-a[f[i][0]-1]==f[i][2]:
            p+=f[i][3]
    if p>s:
        s=p
    a=nex(a,m)
print(s)