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())
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_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    if len(ans)==N:
      ans_list.append(ans)
    else:
      for i in range(x,M+1):
        tmp=deepcopy(ans)
        dfs(i,M,N,tmp)   
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Submission status: Accepted

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

import itertools
ans = 0

for a in itertools.combinations_with_replacement(range(1, m+1), n):
    score = 0
    for j in judge:
        if a[j[1]-1] - a[j[0]-1] == j[2]:
            score += j[3]
    ans = max(ans,score)

print(ans)

Submission status: Accepted

Solution code:
def main(k, s):
    if k == n:
        return sum(d * (s[b] - s[a] == c) for a, b, c, d in abcd)
    return max(main(k + 1, s + [ai]) for ai in range(s[-1], m + 1))

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    print(main(0, [1]))

Submission status: Accepted

Solution code:
import itertools

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


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

print(ans)

Submission status: Accepted

Solution code:
def c():
    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())

    def dfs(lst, depth):
        score = 0
        if len(lst) < depth:
            start = 1 if len(lst) == 0 else lst[-1]
            for m in range(start, M+1):
                score = max(score, dfs(lst + [m], depth))
            return score

        else:
            for i in range(Q):
                score += d[i] if lst[b[i]-1] - lst[a[i]-1] == c[i] else 0
            return score

    A = []
    print(dfs(A, N))


##########
if __name__ == "__main__":
    c()

Submission status: Accepted

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

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

def search(mi, A):
    if len(A) > N:
        return 0

    ret = 0
    for i in range(1, A[-1] + 1):
        ret = max(ret, search(i, A + (i,)))

    d = len(A)
    for b, c, d in BCD[N - d]:
        if A[-(b + 1)] - A[-1] == c:
            ret += d
    return ret

ans = 0
for i in range(1, M + 1):
    ans = max(ans, search(i, (i,)))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n, m, q = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0


def dfs(u, A):
    global n, m, q, l, ans
    if len(A) == n:  # lの長さがnになったらscoreの計算をする
        score = 0
        for i in range(q):
            a, b, c, d = l[i]
            a, b,  = a - 1, b - 1
            if A[b] - A[a] == c:
                score += d
        ans = max(ans, score)
    else:  # 再帰的にリストに番号を追加していく
        for i in range(u, m + 1):
            dfs(i, A + [i])


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

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

def dfs(A: list):
    if len(A) == N:
        arr.append(A)
        return
    start = 1 if len(A) == 0 else A[-1]
    for i in range(start, M+1):
        dfs(A+[i])

dfs([])

ans = 0
for A in arr:
    tmp = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            tmp += d
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())
ans_li = []
abcd = [tuple(map(int,input().split())) for _ in range(Q)]
for A in combinations_with_replacement(range(1,M+1),N):
    ans = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            ans += d
    ans_li.append(ans)
print(max(ans_li))

Submission status: Accepted

Solution code:
def comb(k, s, r):
    if k == n:
        r.append(s[1:])
        return
    for ai in range(s[-1], m + 1):
        comb(k + 1, s + [ai], r)
    return r

def main():
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    s = 0
    for p in comb(0, [1], []):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    main()

Submission status: Accepted

Solution code:
import itertools

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def comb(k, n, m, s, r):
    if k == n:
        r.append(s[1:])
        return
    for ai in range(s[-1], m + 1):
        comb(k + 1, n, m, s + [ai], r)
    return r

def main():
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    s = 0
    for p in comb(0, n, m, [1], []):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    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,b,c,d))
ans=0
p=[]
import sys
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(m-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for i1 in range(1, m+1):
    for i2 in range(i1, m+1):
        for i3 in range(i2, m+1):
            for i4 in range(i3, m+1):
                for i5 in range(i4, m+1):
                    for i6 in range(i5, m+1):
                        for i7 in range(i6, m+1):
                            for i8 in range(i7, m+1):
                                for i9 in range(i8, m+1):
                                    for i10 in range(i9, m+1):
                                        tmp = 0
                                        arrs = [0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        for a, b, c, d in arr:
                                            if arrs[b] - arrs[a] == c:
                                                tmp += d
                                        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
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-1)
  b.append(bb-1)
  c.append(cc)
  d.append(dd)
l=[int(i) for i in range(1,m+1)]
from itertools import combinations_with_replacement
ans=0
for ll in list(combinations_with_replacement(l,n)):
  t=0
  for i in range(q):
    if ll[b[i]]-ll[a[i]]==c[i]:
      t+=d[i]
  ans=max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
# Problem C - Many Requirements

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

# initialization
max_ans = 0

# dfs search
def dfs_score(a_list, p, n, max_ans):
    if p==N:
        tmp_score = 0
        for q in q_list:
            if a_list[q[1]-1]-a_list[q[0]-1]==q[2]:
                tmp_score += q[3]
        max_ans = max(max_ans, tmp_score)
    else:
        for i in range(n, M+1):
            a_list[p] = i
            max_ans = dfs_score(a_list, p+1, i, max_ans)
    return max_ans

# output
a_list = [0]*N
max_ans = dfs_score(a_list, 0, 1, max_ans)
print(max_ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

N, M, Q = map(int, input().split(" "))
que = deque()
for i in range(1, M + 1):
    que.append([i])

while True:
    now = que.popleft()
    if len(now) == N:
        que.append(now)
        break

    last = now[-1] if len(now) > 0 else 1
    for i in range(last, M + 1):
        que.append(now + [i])

cond = []
for _ in range(Q):
    cond.append(tuple(map(int, input().split(" "))))

ans = 0
for seq in que:
    score = 0
    for i in range(Q):
        a, b, c, d = cond[i]
        if seq[b - 1] - seq[a - 1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Accepted

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

vs = []

def dfs(u, A):
    if len(A) == N:
        v = 0
        for j in range(Q):
            a, b, c, d = q[j]
            if A[b-1]-A[a-1] == c:
                v += d
        vs.append(v)
    else:
        for i in range(u, M+1):
            dfs(i, A+[i])
    
dfs(1, [1])
print(max(vs))

Submission status: Accepted

Solution code:
from itertools import permutations, accumulate, combinations, combinations_with_replacement
import sys
input = sys.stdin.readline


def main():
    n, m, q = map(int, input().split())
    # <方針>：Aを全列挙する
    ans = 0
    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
    for A in combinations_with_replacement(range(1, m + 1), n):
        tmp = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp += d[i]
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = 0
N = [i+1 for i in range(m)]

for v in combinations_with_replacement(N,n):
    num = 0
    #print(v)
    for i in range(q):
        if v[b[i]] - v[a[i]] == c[i]:
            num += d[i]
    ans = max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, q = map(int, read().split())
    abcd = [[int(i) for i in read().split()] for _ in range(q)]
    s = 0
    for p in combinations_with_replacement(range(1, m + 1), n):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
t=[list(map(int,input().split())) for _ in range(q)]
ans=0
import itertools
for p in itertools.combinations_with_replacement(range(1,m+1),n):
    d=0
    for i in t:
        if p[i[1]-1]-p[i[0]-1]==i[2]:
            d+=i[3]
    ans=max(d,ans)        
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

def main():
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    s = 0
    for p in combinations_with_replacement(range(1, m + 1), n):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
abcd = [[int(i) for i in input().split()] for _ in range(q)]
s = 0
for p in combinations_with_replacement(range(1, m + 1), n):
    t = 0
    for a, b, c, d in abcd:
        t += d * (p[b - 1] - p[a - 1] == c)
    s = max(s, t)
print(s)

Submission status: Accepted

Solution code:
comb = []
def f(n,cnt,ls):
    if cnt == n:
        comb.append(ls)
        return
    for i in range(ls[cnt-1],m+1):
        tmp = ls.copy()
        tmp[cnt] = i
        f(n,cnt+1,tmp)
    return
ma = lambda :map(int,input().split())
ni = lambda:int(input())

n,m,q = ma()
abcd = []
for i in range(q):
    abcd.append(list(ma()))
ls = [1]*(n+1)
f(n,0,ls)
ans = 0
for A in  comb:
    tmp = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] ==c:
            tmp +=d
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

def calculate(A, abcd):
    total = 0
    for abcdi in abcd:
        a = abcdi[0] - 1
        b = abcdi[1] - 1
        c = abcdi[2]
        d = abcdi[3]
        if A[b] - A[a] == c:
            total += d
    # print(A, total)

    return total

A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# print(A)

maximum = max([calculate(Ai, abcd) for Ai in A])

print(maximum)

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,b,c,d))
ans=0
import itertools
p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = list(map(int, input().split()))
abcd = [list(map(int, input().split())) for i in range(Q)]
# print(N, M, Q)
# print(abcd)

def calculate(A, abcd):
    total = 0
    for abcdi in abcd:
        a = abcdi[0] - 1
        b = abcdi[1] - 1
        c = abcdi[2]
        d = abcdi[3]
        if A[b] - A[a] == c:
            total += d
    # print(A, total)

    return total

import itertools
A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# print(A)

maximum = 0
for Ai in A:
    maximum = max(calculate(Ai, abcd), maximum)

print(maximum)

Submission status: Accepted

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

def score(A):
  scr = 0
  for a,b,c,d in abcd:
    if A[b]-A[a] == c:
      scr += d
  return scr 

def dfs(A,LEN):
  if LEN == n:
    global ans
    tmp = score(A)
    ans = max(ans, tmp)
  else:
    for i in range(A[-1],m+1):
      dfs(A+[i],LEN+1)

dfs([1],0)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for a in itertools.combinations_with_replacement(range(1, m+1), n):
    temp = 0
    for i in range(q):
        ai, bi, ci, di = kumi[i]
        ai, bi = ai-1, bi-1
        if a[bi] - a[ai] == ci:
            temp += di
    ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
def LI():return list(map(int,input().split()))
n,m,q=LI()
abcd=[]
for _ in range(q):
  a,b,c,d=LI()
  a-=1
  b-=1  
  abcd.append((a,b,c,d))
As=itertools.combinations_with_replacement(range(1,m+1),n)
#重複組み合わせ [1,2,3,4...m]から重複を許してn個取ってくる
ans=0

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

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
A = list(itertools.combinations_with_replacement(range(1, M + 1), N))
B = []
# print(len(list(A)))
for a in A:
    for j in range(N - 1):
        flag = True
        if a[j] > a[j + 1]:
            flag = False
            break
    if flag:
        B.append(a)

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

for i in range(Q):
    o, p, q, r = map(int, input().split())
    o -= 1
    p -= 1
    a.append(o)
    b.append(p)
    c.append(q)
    d.append(r)

ans = 0
for li in B:
    tmp = 0
    for i in range(Q):
        if li[b[i]] - li[a[i]] == c[i]:
            tmp += d[i]
    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
for x in combinations_with_replacement(range(1, M + 1), N):
    tmp = 0
    for i in range(Q):
        if x[X[i][1] - 1] - x[X[i][0] - 1] == X[i][2]:
            tmp += X[i][3]
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

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)

num = [0] * (n+1)

# dfs([1])
dfs2(1)
print(ans)

Submission status: Accepted

Solution code:

import itertools

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

ans = 0
for ite in itertools.combinations_with_replacement(range(1,M+1), N):
    val = 0
    for q in data:
        if ite[q[1]-1] - ite[q[0]-1] == q[2]:
            val += q[3]
    ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for A in itertools.combinations_with_replacement(range(1, M + 1), N):
    ans = max(sum([d for (a, b, c, d) in qs if A[b - 1] - A[a - 1] == c]), ans)

print(ans)

Submission status: Accepted

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


def dfs(x):
    if len(x) == N + 1:
        tmp = 0
        for i in range(Q):
            if x[X[i][1]] - x[X[i][0]] == X[i][2]:
                tmp += X[i][3]
        return tmp

    x.append(x[-1])
    res = 0
    while x[-1] <= M:
        res = max(res, dfs(x))
        x[-1] += 1
    x.pop()

    return res

print(dfs([1]))

Submission status: Accepted

Solution code:
from itertools import *

n, m, q = map(int, input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int, input().split())))
    abcd[i][0] -= 1
    abcd[i][1] -= 1

numbers = []
for i in range(1, m + 1):
    numbers.append(i)
    
cwr = list(combinations_with_replacement(numbers, n))

ans = 0
for c in cwr:
    cnt = 0
    for i in range(q):
        if c[abcd[i][1]] - c[abcd[i][0]] == 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())
lis=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    lis.append((a,b,c,d))
    
from itertools import combinations_with_replacement

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

ans=0
for status in co:
    tmp_score=0
    for a,b,c,d in lis:
        if status[b-1]-status[a-1]==c:
            tmp_score+=d
    ans=max(ans,tmp_score)
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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

A = [i for i in range(1,m+1)]
sum = 0

for k in itertools.combinations_with_replacement(A,n):
  sum_tmp = 0
  for i in range(q):
    if k[a[i][1] - 1] - k[a[i][0] - 1] == a[i][2]:
        sum_tmp += a[i][3]
  
  if sum_tmp > sum:
    sum = sum_tmp

print(sum)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力の取得
N, M, Q = list(map(int, input().split()))
a, b, c, d = [], [], [], []
for q in range(Q):
    a_q, b_q, c_q, d_q = list(map(int, input().split()))
    a.append(a_q)
    b.append(b_q)
    c.append(c_q)
    d.append(d_q)


def get_score(A: tuple) -> int:
    """得点を計算するメソッド

    Arguments:
        A {tuple} -- 数列

    Returns:
        int -- 得点
    """
    score = 0
    for a_i, b_i, c_i, d_i in zip(a, b, c, d):
        score += (A[b_i-1] - A[a_i-1] == c_i) * d_i
    return score


def main() -> None:
    """Entry point
    """
    # 求解処理
    # 条件を満たす数列を全探索
    l = list(range(1, M+1))
    result = 0
    for A in itertools.combinations_with_replacement(l, N):
        result = max(result, get_score(A))

    # 結果出力
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

list = []
for i in range(1, m+1):
    list.append(i)
 
 
wa = 0
ans = 0
 
for i in itertools.combinations_with_replacement(list, n):
    for a,b,c,d in abcd:
        # print(a,b,c,d)
        # if a <= len(i) and b <= len(i):
        if i[b-1]-i[a-1]==c:
            wa += d
            ans = max(ans, wa)
    wa = 0
 
print(ans)

Submission status: Accepted

Solution code:
import queue

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

q = queue.Queue()
q.put([1])
while not q.empty():
    p = q.get()
    if len(p)==n+1:
        q.put(p)
        break
    for i in range(p[-1],m+1):
        q.put(p+[i])

ans = 0
while not q.empty():
    p = q.get()
    score = 0
    for a,b,c,d in g:
        if p[b]-p[a] == c:
            score += d
    ans = max(score,ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

op = []

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

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

ans = 0
for arr in combinations_with_replacement(array, n):
    score = 0
    for a, b, c, d in op:
        if arr[b - 1] - arr[a - 1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    n, m, q = map(int, input().split())
    cond = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    for i in itertools.combinations_with_replacement(range(1, m+1), n):
        point = 0
        for j in range(q):
            if i[cond[j][1]-1] - i[cond[j][0]-1] == cond[j][2]:
                point += cond[j][3]
        ans = max(ans, point)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    n, m, q = map(int, input().split())
    cond = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    for i in list(itertools.combinations_with_replacement(range(1, m+1), n)):
        point = 0
        for j in range(q):
            if i[cond[j][1]-1] - i[cond[j][0]-1] == cond[j][2]:
                point += cond[j][3]
        ans = max(ans, point)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def resolve():
    import itertools
    n, m, q = map(int, input().split())
    cond = [list(map(int, input().split())) for _ in range(q)]
    #pos = list(itertools.combinations_with_replacement(range(1, m+1), n))
    ans = 0
    for i in list(itertools.combinations_with_replacement(range(1, m+1), n)):
        #test = list(pos[i])
        point = 0
        for j in range(q):
            if i[cond[j][1]-1] - i[cond[j][0]-1] == cond[j][2]:
                point += cond[j][3]
        ans = max(ans, point)
    print(ans)
resolve()

Submission status: Accepted

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

abcd = []
for i in range(q):
    abcd.append(tuple(map(int, input().split())))

ans = 0


def solve(A):
    if len(A) >= n + 1:
        global ans
        now = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                now += d
        ans = max(ans, now)
        return
    for i in range(A[-1], m + 1):
        solve(A + [i])


solve([1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as com
n, m, q = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(q)]
x = []
for i in range(m):
    x.append(i+1)
y = list(com(x, n))
ans = 0
for i in y:
    tmp = 0
    for a, b, c, d in arr:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
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)]
ac=tuple([i for i in range(1,m+1)])
ans=0
for A in list(itertools.combinations_with_replacement(ac,n)):
    count=0
    for j in range(q):
        if A[a[j][1]-1]-A[a[j][0]-1]==a[j][2]:
            count+=a[j][3]
    ans=max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
# C - Many Requirements

from itertools import combinations_with_replacement

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

x = max(sum(d for a, b, c, d in lst if seq[b-1] - seq[a-1] == c)
        for seq in combinations_with_replacement(range(1, m+1), n))
print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M,Q=MI()
    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]=MI()
    
    #dfsの数列生成
    st=[]
    st2=[]
    for i in range(1,M+1):
        st.append([i])
    
    for dig in range(N):
        while len(st)!=0:
            L=st.pop()
            v=L[-1]
            for i in range(v,M+1):
                st2.append(L+[i])
                
        while len(st2)!=0:
            L=st2.pop()
            st.append(L)
            
    ans=0
    for i in range(len(st)):
        L=st[i]
        temp=0
        for j in range(Q):
            if L[b[j]-1]-L[a[j]-1]==c[j]:
                temp+=d[j]
        ans=max(ans,temp)
    print(ans)
    
    
    
main()

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple
from typing import List

sys.setrecursionlimit(2 ** 20)


R = namedtuple('R', 'a b c d')

N, M, Q = map(int, input().split())
requirements: List[R] = []

for _ in range(Q):
  a, b, c, d = map(int, input().split())
  requirements.append(R(a, b ,c, d))

max_score = 0

def dfs(A):
  global max_score
  if len(A) > N + 1:
    score = 0
    for a, b, c, d in requirements:
      if A[b] - A[a] == c:
        score += d
    max_score = max(max_score, score)
    return
  for i in range(A[-1], M + 1):
    dfs(A + [i])

dfs([1])
print(max_score)

Submission status: Accepted

Solution code:
import itertools

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

def check(l):
  res = 0
  for a,b,c,d in abcd:
    a -= 1
    b -= 1
    if l[b]-l[a] == c:
      res += d
  return res

l = itertools.combinations_with_replacement(range(1,m+1),n)
ans = 0
for li in l:
  ans = max(check(li),ans)
print(ans)

Submission status: Accepted

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

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

ans = 0
def dfs(l):
  global ans
  if len(l) == n:
    ans = max(check(l),ans)
  else:
    if len(l) == 0:
      mx = 1
    else:
      mx = l[-1]
    for i in range(mx,m+1):
      tmpl = l + [i]
      dfs(tmpl)

def check(l):
  res = 0
  for a,b,c,d in abcd:
    a -= 1
    b -= 1
    if l[b]-l[a] == c:
      res += d
  return res

dfs([])
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)]
 
ms=[i for i in range(1,m+1)]
ans=0
for k in itertools.combinations_with_replacement(ms, n):
  x=0
  for j in range(q):
    if a[j][2]==k[a[j][1]-1]-k[a[j][0]-1]:
      x+=a[j][3]
  if ans<x:
    ans=x
print(ans)

Submission status: Accepted

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

import itertools
cr = itertools.combinations_with_replacement(range(1, m+1), n)
M = 0
for seq in cr:
  score = sum([d for a, b, c, d in abcd if seq[b-1] - seq[a-1] == c])
  M = max(M, score)
print(M)

Submission status: Accepted

Solution code:
def judge():
    global num, a, b, c, d, q
    point = 0
    for i in range(q):
        if (num[b[i]] - num[a[i]] == c[i]):
            point += d[i]
    return point


def mk_num(i):
    global mx_p
    global m
    for j in range(num[i-1], m):
        num[i] = j
        if (i == n):
            tmp = judge()
            if (mx_p < tmp):
                mx_p = tmp
        else:
            mk_num(i+1)


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())

num = [0] * (n+1)
mx_p = 0

mk_num(1)
print(mx_p)