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())
Ques = [ list(map(int, input().split())) for _ in range(Q) ]

Nums = [ i for i in range(M) ]
ans = -1
for v in combinations_with_replacement(Nums, N):
    cnt = 0
    for que in Ques:
        if v[que[1]-1]-v[que[0]-1] == que[2]: cnt += que[3]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
length, Max, q = map(int,input().split())
query = [[0]*4 for _ in range(q)]
for i in range(q):
    a,b,c,d = map(int,input().split())
    query[i] = [a-1,b-1,c,d]
ans = 0
def dfs(A):
    if len(A) == length:
        global ans
        score = 0
        for i in range(q):
            a,b,c,d = query[i]
            if A[b] - A[a] == c:
                score += d
        ans = max(ans, score)
        return
    last = A[-1]
    for i in range(last,Max+1):
        A.append(i)
        dfs(A)
        A.pop()
dfs([1])
print(ans)

Submission status: Accepted

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

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

a = [1]*n
def next_a(a):
    if a[-1] != m:
        a[-1] += 1
    else:
        d = n-1
        while d > 0 and a[d] == m:
            d-=1
        if d < 0:
            return a
        a[d] += 1
        next = a[d]
        for i in range(d,n):
            a[i] = next
max = -1
a[-1] = 0
while sum(a) != n*m:
    next_a(a)
    test = 0
    for i in range(q):
        if a[abcd_list[i][1]-1] - a[abcd_list[i][0]-1] == abcd_list[i][2]:
            test += abcd_list[i][3] 
    if test > max:
        max = test

print(max)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

A_lst = combinations_with_replacement(range(1, M+1), N)
A_lst = list(map(list, A_lst))
A_lst.sort()

dm = 0 #d_sum_max
for A in A_lst:
    ds = 0 #d_sum
    for a, b, c, d in lst:
        if A[b-1] - A[a-1] == c:
            ds += d
    if ds > dm:
        dm = ds
print(dm)

Submission status: Accepted

Solution code:
n, m, q = list(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

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

def dfs(A):
    if len(A)==n:
        #print(A)
        return score(A)
    res = 0
    if len(A) > 0:
        last_term = A[-1]
    else:
        last_term = 1
    for i in range(last_term, m+1):
        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())
    a[i] -= 1  #a,bを0オリジンにそろえる
    b[i] -= 1  

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

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

print(dfs([]))

Submission status: Accepted

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


def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return

    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)


ans, tempAns = 0, 0
for tempA in combinations_with_replacement(range(1, m + 1), n):
    tempAns = 0
    for a in A:
        if tempA[a[1] - 1] - tempA[a[0] - 1] == a[2]:
            tempAns += a[3]
    ans = max(ans, tempAns)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for q in range(Q)]
print(max(sum(d for a,b,c,d in abcd if i[b-1]-i[a-1]==c) for i in combinations_with_replacement(range(M),N)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], n)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            _temp += d

    ans = max(ans, _temp)

print(ans)

Submission status: Accepted

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

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

def dfs(pre, _min):
    if len(pre) == n:
        return score(pre)
    ret = 0
    for i in range(_min, m+1):
        new = pre + [i]
        ret = max(ret, dfs(new, i))
    return ret

print(dfs([], 1))

Submission status: Accepted

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

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

ans = 0
while A[0] <= m:
    tmp = 0
    for i in range(q):
        if (A[b[i]-1] - A[a[i]-1]) == c[i]:
            tmp += d[i]
    if tmp > ans:
        ans = tmp
    
    A[-1] +=1
    for i in range(n-1,0,-1):
        if A[i] == m+1:
            A[i-1] +=1
            for j in range(len(A[i:])):
                A[i+j] = A[i-1]
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

L = [i+1 for i in range(m)]
li = [input().split() for i in range(q)]

for i in range(q):
    li[i] = [int(x) for x in li[i]]

ans = 0
for v in combinations_with_replacement(L,n):
    sum1 = 0
    for i in li:
        if v[i[1]-1] - v[i[0]-1] == i[2]:
            sum1 +=i[3]
    ans = max(ans,sum1)
print(ans)

Submission status: Accepted

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

ans = 0
A = []


def dfs():
    global A, ans
    if len(A) == N:
        res = sum(t[3] for t in L if A[t[1]-1] - A[t[0]-1] == t[2])
        ans = max(ans, res)
    else:
        for a in range(A[-1] if A else 1, M + 1):
            A.append(a)
            dfs()
            A.pop()


dfs()
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):
                                        suuretsu = [i1, i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        tmp = 0
                                        for a,b,c,d in arr:
                                            if suuretsu[b-1] - suuretsu[a-1] == 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):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

L = []
def dfs(S):
    if len(S) == N:
        L.append(S)
    elif S == "":
        for i in range(M):
            S = str(i)
            dfs(S)
    else:
        for i in range(int(S[-1]), M):
            dfs(S+str(i))
dfs("")

Ans = 0
for l in L:
    ans = 0
    for a, b, c, d in zip(A,B,C,D):
        if int(l[b-1]) - int(l[a-1]) == c:
            ans += d
    Ans = max(ans, Ans)
print(Ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

for i in range(Q):
    num.append(list(map(int, input().split())))

lst = list(combinations_with_replacement([i for i in range(1, M+1)], N))

ans = 0
for q in lst:
    ans_tmp = 0
    
    for i in range(Q):
        if(q[num[i][1]-1]-q[num[i][0]-1] == num[i][2]):
            ans_tmp += num[i][3]
    
    if(ans < ans_tmp):
        ans = ans_tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    abcd = []
    for _ in range(q):
        q = tuple(map(int, input().split()))
        abcd.append(q)
    c1 = tuple(combinations_with_replacement(range(1,m+1), n))
    r = 0
    for ce in c1:
        t = 0
        for qe in abcd:
            a, b, c, d = qe
            a -= 1
            b -= 1
            if ce[b] - ce[a] == c:
                t += d
        r = max(r, t)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

ans = 0

for a_temp in temp:
    ans_temp = 0
    for i in range(q):
        if a_temp[a[i][1]-1] - a_temp[a[i][0]-1] == a[i][2]:
            ans_temp += a[i][3]
    if ans < ans_temp:
        ans = ans_temp
        
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys

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

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
            return
        for v in range(A[-1] if A else 1, M + 1):
            A.append(v)
            dfs(A)
            A.pop()
    
    input = sys.stdin.readline

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

    ans = 0
    dfs([])
    print(ans)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys
    from itertools import combinations_with_replacement

    input = sys.stdin.readline

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

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

    print(ans)


main()

Submission status: Accepted

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

def main():
    import sys

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

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
        elif len(A) == 0:
            for nx in range(1, M + 1):
                dfs(A + [nx])
        else:
            for nx in range(A[-1], M + 1):
                dfs(A + [nx])

    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(Q)]
    ans = 0
    dfs([])
    print(ans)


main()

Submission status: Accepted

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

def main():
    import sys

    sys.setrecursionlimit(10 ** 8)
    
    def calc(A: list):
        score = 0
        for a, b, c, d in lst:
            if A[b - 1] - A[a - 1] == c:
                score += d
        return score

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
        elif len(A) == 0:
            for nx in range(1, M + 1):
                dfs(A + [nx])
        else:
            for nx in range(A[-1], M + 1):
                dfs(A + [nx])

    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(Q)]
    ans = 0
    dfs([])
    print(ans)


main()

Submission status: Accepted

Solution code:
import copy

def cnt(a, m, i):
    if a[i] < m:
        a[i] += 1
    else:
        a = cnt(a, m, i-1)
        a[i] = copy.deepcopy(a[i-1])
    return a

def check(a, ab):
    score = 0
    for i in range(q):
        ai, bi = ab[i][0], ab[i][1]
        if a[bi] - a[ai] == ab[i][2]:
            score += ab[i][3]
    return score
  
n, m, q = map(int,input().split())
ab = []
for i in range(q):
    ab.append(list(map(int,input().split())))

a = [1] * (n+1)
a[0] = 0
ans = 0
while a[0] == 0:
    x = check(a, ab)
    ans = max(ans, x)
    # print(a, ans)
    a = cnt(a, m, -1)
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,m,q=map(int,input().split())
l=[i for i in range(1,m+1)]
ab=[list(map(int,input().split())) for _ in range(q)]
ans=0
for res in itertools.combinations_with_replacement(l, n):
    ans_r=0
    for i in range(q):
        a,b,c,d=ab[i]
        if c==res[b-1]-res[a-1]:
            ans_r+=d
    ans=max(ans,ans_r)
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:
        res = 0
        for a, b, c, d in X:
            if x[b] - x[a] == c:
                res += d
        return res

    res = 0
    for n in range(x[-1], M + 1):
        x.append(n)
        res = max(res, dfs(x))
        x.pop()
    return res


print(dfs([1]))

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:
from itertools import combinations_with_replacement as c_w_r
N,M,Q=map(int,input().split())
s=[list(map(int,input().split()))for _ in range(Q)]
ans=0
for i in c_w_r([i for i in range(1,M+1)],N):
  e=0
  for a,b,c,d in s:
    if i[b-1]-i[a-1]==c:
      e+=d
  ans=max(ans,e)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for x 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:
import copy

N, M, Q = list(map(int, input().split()))
a = [0] * Q

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

mscore = 0

def createArray(num,arr):
    global mscore
    arr.append(num)
    if len(arr) < N:
        for i in range(num,M+1):
            arrr = copy.deepcopy(arr)
            createArray(i,arrr)
    else:
        score = 0
        for item in a:
            if arr[item[1]-1] - arr[item[0]-1] == item[2]:
                score += item[3]
        mscore = max(mscore, score)

for i in range(M):
    arr = []
    createArray(i+1,arr)

print(mscore)

Submission status: Accepted

Solution code:
import itertools
# import math
# import sys
# import numpy as np

# K = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M, Q = map(int, input().split())
# A = list(map(int, input().split()))
# Q = list(map(int, input().split()))
# S = input()

# d = sorted(d.items(), key=lambda x:x[0]) # keyでsort

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

# all_cases = list(itertools.permutations(P))
a = list(itertools.combinations_with_replacement([i for i in range(1, M + 1)], N))
# print(a[0][0])
# print(conditions[0])

max_score = 0
for t in a:
    tot = 0
    for condition in conditions:
        if t[condition[1] - 1] - t[condition[0] - 1] == condition[2]:
            tot += condition[3]
    if tot > max_score:
        max_score = tot
print(max_score)

Submission status: Accepted

Solution code:
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n,m,q =map(int, input().split())
qs = []
ans = 0
for i in range(q):
    arr= list(map(int, input().split()))
    qs.append(arr)
    
def calc(x):
    global ans
    tmp = 0
    for i in range(q):
        if(x[qs[i][1]-1]-x[qs[i][0]-1]==qs[i][2]):
            tmp+=qs[i][3]
    ans = max(ans, tmp)

def dfs(x):
    if(len(x)==n):
        calc(x)
    else:
        for i in range(x[-1], m+1):
            x.append(i)
            dfs(x)
            x.pop()
dfs([1])
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], b[i] = a[i] - 1, b[i] - 1

ans = 0

def calc(x):
    global ans
    score = 0
    for i in range(q):
        if x[b[i]] - x[a[i]] == c[i]:
            score += d[i]
    ans = max(ans, score)

def dfs(x):
    if len(x) == n:
        calc(x)
        return

    for i in range(x[-1], m+1):
        x.append(i)
        dfs(x)
        x.pop()

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
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], b[i] = a[i] - 1, b[i] - 1

p_tmp = [0] * m
for i in range(m):
    p_tmp[i] = i

p = combinations_with_replacement(p_tmp, n)

ans = 0
for x in p:
    score = 0
    for i in range(q):
        if x[b[i]] - x[a[i]] == c[i]:
            score += d[i]

    ans = max(ans, score)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
a_list = []
b_list = []
c_list = []
d_list = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

import itertools

ans = 0
h_list = [i+1 for i in range(m)]
for A in itertools.combinations_with_replacement(h_list, n):
    # print(A)
    max_d = 0
    for a, b, c, d in zip(a_list, b_list, c_list, d_list):
        if A[b-1]-A[a-1] == c:
            max_d += d
    ans = max(ans, max_d)

print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import combinations_with_replacement
def resolve():
    n, m, q = map(int, input().split())
    ABCD = [tuple(map(int, input().split())) for _ in range(q)]
    ans = 0
    for I in combinations_with_replacement(range(m), n):
        score = 0
        for a, b, c, d in ABCD:
            if I[b - 1] - I[a - 1] == c:
                score += d
        ans = max(ans, score)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cr
n,m,q=map(int,input().split())
s=[list(map(int,input().split()))for i in range(q)]
f=0
for i in cr([i for i in range(1,m+1)],n):
    e=0
    for a,b,c,d in s:
        if i[b-1]-i[a-1]==c:
            e+=d
    if f<e:f=e
print(f)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]
a_list = []
ans = 0

for i in itertools.combinations_with_replacement(range(1,M+1),N):
    ans2 = 0
    for t in A:
        if i[t[1]-1] - i[t[0]-1] == t[2]:
            ans2 += t[3]

    ans = max(ans,ans2)

print(ans)

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, b, c, d = map(int, input().split())
    A[i] = a
    B[i] = b
    C[i] = c
    D[i] = d
X = list(itertools.combinations_with_replacement([a for a in range(1,M+1)],N))

cnt = [0] * (len(X))
for k in range(len(X)):
    for l in range(Q):
        if X[k][B[l] - 1] - X[k][A[l] - 1] == C[l]:
            cnt[k] += D[l]

print(max(cnt))

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

mx = 0

def dfs(Aary):
    global mx

    if len(Aary) == N + 1:
        scr = score(Q, Aary, a, b, c, d)
        if mx < scr:
            mx = scr
        return

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

def score(Q, A, a, b, c, d):
    ans = 0
    for i in range(Q):
        if A[b[i]] - A[a[i]] == c[i]:
            ans += d[i]

    return ans

dfs( [1] )

print(mx)

Submission status: Accepted

Solution code:
import itertools

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

def get_sum(A, abcd_array):
    sum = 0
    for abcd in abcd_array:
        a, b, c, d = abcd
        if A[b-1] - A[a-1] == c:
            sum += d
    return sum

candidate_array = list(itertools.combinations_with_replacement(range(1,m+1), n))
ans = 0
for A in candidate_array:
    ans = max(ans, get_sum(A, abcd_array))

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

lists = list(itertools.combinations_with_replacement(range(1, m+1), n))
#print(lists)
max_point = 0
for each in lists:
  point = 0
  for i in range(q):
    l = lst[i]
    a = l[0] - 1
    b = l[1] - 1
    c = l[2]
    if each[b] - each[a] == c:
      point += l[3]
  if point > max_point:
    max_point = point
print(max_point)

Submission status: Accepted

Solution code:
def main():
    N, M, Q = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(Q)]

    def dfs(A):
        if len(A) == N:
            ret = 0
            for (a, b, c, d) in T:
                if A[b-1] - A[a-1] == c:
                    ret += d
            return ret
        ret = 0
        s = A[-1] if A else 1
        for a in range(s, M+1):
            ret = max(ret, dfs(A + [a]))
        return ret

    print(dfs([]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a_ls=[]
b_ls=[]
c_ls=[]
d_ls=[]

for vnwrjvnwakn in range(Q):
	abcd=list(map(int, input().split()))
	a_ls+=[abcd[0]]
	b_ls+=[abcd[1]]
	c_ls+=[abcd[2]]
	d_ls+=[abcd[3]]



import itertools
As=itertools.combinations_with_replacement(range(1,M+1),N)
ans=0
for A in As:
	score=0
	Als=list(A)
	for i in range(Q):
		if Als[b_ls[i]-1]-Als[a_ls[i]-1]==c_ls[i]:
			score+=d_ls[i]
	
	ans=max(ans,score)


print(ans)

Submission status: Accepted

Solution code:
number=list(map(int,input().split()))
n,m,q=number[0],number[1],number[2]
nums=[]
for i in range(q):
    tmp=list(map(int,input().split()))
    nums.append(tmp)
answer=0
mid=0
List1=[]
for i in range(m):
  List1.append(i)
import itertools
for i in list(itertools.combinations_with_replacement(List1,n)):
    mid=0
    for j in range(q):
        if i[nums[j][1]-1]-i[nums[j][0]-1]==nums[j][2]:
            mid+=nums[j][3]
    answer=max(mid,answer)
    
print(answer)

Submission status: Accepted

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comp_rplc

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

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

ans = 0

for seq in comp_rplc(range(1, m + 1), n):
  score = 0
  for a, b, c, d in req:
    if seq[b - 1] - seq[a - 1] == c:
      score += d
    
  ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int,input().split())
List = []
for i in range (Q):
  List.append(list(map(int, input().split())))
List1 = []
res = 0
mid = 0
for i in range(M):
  List1.append(i)
x = itertools.combinations_with_replacement(List1, N)
tryList= list(x)

for tryElement in tryList:
  mid = 0
  for j in range(Q):
    if tryElement[List[j][1]-1]-tryElement[List[j][0]-1]==List[j][2]:
      mid += List[j][3]
  res = max(mid,res)
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(list(map(int, input().split())))
ans = 0
def dfs(n):
    if len(n) == N+1:
        global ans
        tmp = 0
        for i in range(Q):
            abi = n[l[i][1]]
            aai = n[l[i][0]]
            c = l[i][2]
            d = l[i][3]
            if abi -aai == c:
                tmp += d
        ans = max(ans, tmp)
    else:
        for i in range(n[-1], M+1):
            tmp2 = n[:]
            tmp2.append(i)
            dfs(tmp2)
dfs([1])
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 arr in combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    arr = list(arr)
    for a, b, c, d in X:
        if arr[b - 1] - arr[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

import itertools
for con in itertools.combinations_with_replacement(list(range(m)),n):
    tmp = 0
    for i in query:
        a,b,c,d = i
        if con[b-1] - con[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)]

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

print(ans)

Submission status: Accepted

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


def main():
  N, M, Q = list(map(int, input().split()))
  cands = itertools.combinations(range(N+M-1), N)
  Qs = [tuple(map(int, input().split())) for _ in range(Q)]

  seq = [0]*N
  max_ = 0
  for cand in cands:
    temp_max = 0
    for i in range(N):
      seq[i] = cand[i] - i

    for a, b, c, d in Qs:
      if seq[b-1] - seq[a-1] == c:
        temp_max += d
    max_ = max(max_, temp_max)

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
L=list(itertools.combinations_with_replacement(range(m),n))
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=0
for l in L:
    tmp=0
    for i in range(q):
        if l[b[i]]-l[a[i]]==c[i]:
            tmp+=d[i]
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

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

def dfs(A, head):
  if len(A) == N:
    score = 0
    for a, b, c, d in cond:
      if A[b] - A[a] == c:
        score += d
    return score
  ans = 0
  for n in range(head, M + 1):
    ans = max(ans, dfs(A + [n], n))
  return ans
print(dfs([1], 1))