Problem:


Score : 300 points

Problem Statement

Given are positive integers N, M, Q, and Q quadruples of integers ( a_i , b_i , c_i , d_i ).

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.

Let us define a score of this sequence as follows:

The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i. (If there is no such i, the score is 0.)

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
import itertools
#K = int(input())
N,M,Q = map(int,input().split())
#N = str(input())
#A = list(map(int,input().split()))
nums=[i for i in range(1,M+1)]
count=0
inp=[]
for i in range(Q):
    I=list(map(int,input().split()))
    inp.append(I)

for v in itertools.combinations_with_replacement(nums, N):
    c=0
    v=list(v)
    for i in inp:

        if v[i[1]-1] - v[i[0]-1]==i[2]:
            c+=i[3]
    count=max(count,c)
print(count)

Submission status: Accepted

Solution code:
import itertools

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

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

print(ans)

Submission status: Accepted

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

max_ans = 0
for mid in itertools.combinations_with_replacement(range(1,m+1), n):
    sum_ans=0
    for q in qs:
        if mid[q[1]-1]-mid[q[0]-1] == q[2]:
            sum_ans += q[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement


def getPoint(data, A, q):
    res = 0
    for i in range(q):
        a, b, c, d = data[i]
        if A[b]-A[a] == c:
            res += d
    return res

def main():
    n, m, q = map(int, readline().split())    
    data = []
    for _ in range(q):
        a, b, c, d = map(int, readline().split())
        a-=1
        b-=1
        data.append((a, b, c, d))
    p = [int(i) for i in range(1, m+1)]
    ans = 0
    for A in combinations_with_replacement(p, n):
        ans = max(getPoint(data, A, q), ans)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
def main():
    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 = list(itertools.combinations_with_replacement([i for i in range(1,M+1)], N))
    D = []
    for f in A:
        e=0
        for i in range(Q):
            if f[b[i]-1]-f[a[i]-1] == c[i]:
                e = e + d[i]
        D.append(e)
    print(max(D))
main()

Submission status: Accepted

Solution code:
import itertools
N, M, Q  = map(int,input().split())
query = []
for q in range(Q):
    a,b,c,d = map(int,input().split())
    a-=1
    b-=1
    query.append((a,b,c,d))
mx = 0
for comb in itertools.combinations_with_replacement([i for i in range(1,M+1)],N):
    score = 0
    for a,b,c,d in query:
        if (comb[b] - comb[a] == c):
            score += d
    mx = max(score,mx)
print (mx)

Submission status: Accepted

Solution code:
def dfs(l, A):
    for i, val in enumerate(l):
        A.append(val)
        if len(A) == N:
            As.append(A)
            A = A.copy()
            A.pop()
        else:
            sub_l = l[i:]
            A = dfs(sub_l, A)
            A.pop()
    return A


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

l = list(range(1, M + 1))
As = []
A = []
_ = dfs(l, A)

ans = 0
for A in As:
    # i=0; A = As[i]
    score = 0
    for i, l in enumerate(ls):
        # i=0; l=ls[i]
        if A[l[1] - 1] - A[l[0] - 1] == l[2]:
            score += l[3]
    if score >= ans:
        ans = score

print(ans)

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)]
l=range(1,m+1)
h_list = list(itertools.combinations_with_replacement(l, n))
ans=0
for i in h_list:
    b=0
    for j in a:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            b+=j[3]
    ans=max(ans,b)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd_lis = []
for i in range(Q):
	abcd_lis.append(list(map(int, input().split())))
lis = [i+1 for i in range(M)]

lis = list(itertools.combinations_with_replacement(lis, N))
maxi = 0
for i in lis:
  count = 0
  for j in range(Q):
    idx1 = abcd_lis[j][0]-1
    idx2 = abcd_lis[j][1]-1
    if i[idx2]-i[idx1] == abcd_lis[j][2]:
      count += abcd_lis[j][3]
  if maxi < count:
    maxi = count
print(maxi)

Submission status: Accepted

Solution code:
import itertools
def generateA(N, M, minv=1):
    if N < 0:
        return
    if N == 0:
        yield []
    if N == 1:
        for i in range(minv, M):
            yield [i]
    for v in range(minv, M+1):
        for subA in generateA(N-1, M, v):
            yield [v] + subA

def point(A, L):
    result = 0
    for (a, b, c, d) in L:
        if A[b-1] - A[a-1] == c:
            result += d

    return result

def summary(N, M, L):
    As = generateA(N, M)

    results = []
    for A in As:
        results.append(point(A,L))
    return results

def test():
    As = generateA(3,4)
    for A in As:
        print(A)

def main():
    #test()
    N, M ,Q = map(int, input().split())
    L = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        L.append((a,b,c,d))
    results = summary(N,M,L)

    print(max(results))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

def dfs(v,pre):
    global ans
    if len(v) >= n:
        cnt = 0
        for a,b,c,d in abcd:
            if (v[b-1] - v[a-1] == c):
                cnt += d
        ans = max(ans, cnt)
        return 

    for i in range(pre, m+1):
        v.append(i);
        dfs(v, i)
        v.pop(-1)


v = [1]
dfs(v,1)
print(ans)

Submission status: Accepted

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

def score(lists):
    tmp = 0
    for i in T:
        if lists[i[1] - 1] - lists[i[0] - 1] == i[2]:
            tmp += i[3]
    return tmp
        
def make_lists(lists=[], s=0, ans=0, times=0):
    if times == N:
        return score(lists)

    for i in range(s, M):
        ans = max(ans, make_lists(lists + [i], i, ans, times + 1))
    return ans
        
print(make_lists())

Submission status: Accepted

Solution code:
import itertools

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

def score(seq):
  s = 0
  for q in range(Q):
    if seq[cmb[q][1]-1] - seq[cmb[q][0]-1] == cmb[q][2]:
      s += cmb[q][3]
  return s

p = [i for i in range(1, M+1)]
A = itertools.combinations_with_replacement(p, N)
ans = 0
for a in A:
  ans = max(ans, score(a))
print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,M,Q = inputlist()
l = [0]*Q
for i in range(Q):
    l[i] = inputlist()
li = [int(i) for i in range(1,M+1)]
from itertools import combinations_with_replacement
h = combinations_with_replacement(li,N)
ans = 0
for v in h:
    va = list(v)
    tmp = 0
    for i in range(Q):
        a,b,c,d = l[i]
        a-=1
        b-=1
        if va[b] - va[a] == c:
            tmp += d
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


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

Submission status: Accepted

Solution code:
import itertools
n, m, q = list(map(int, input().split()))
ary = []
point_max=0
for i in range(q):
    ary.append(list(map(int, input().split())))

l = list(range(1, m+1))
# 全パターン網羅
for v in itertools.combinations_with_replacement(l, n):
    point=0
    # 得点計算
    for j in ary:
        if v[j[1]-1]-v[j[0]-1]==j[2]:
            point+=j[3]
    if point_max < point:
        point_max = point
print(point_max)

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())
    
numbers = range(1, m+1)
arrays = list(combinations_with_replacement(numbers, n))
ans = []


for i in range(len(arrays)):
    dm = 0
    l = arrays[i]
    for j in range(q):
        if l[b[j]-1] - l[a[j]-1] == c[j]:
            dm = dm+d[j]
    ans.append(dm)
    
print(max(ans))

Submission status: Accepted

Solution code:
import itertools

n,m,q = input().split()
n = int(n)
m = int(m)
q = int(q)
num_list = []
a = list(range(1, n+1))
for i in range(q):
    num_list.append(list(map(int,input().split())))
ff = list(itertools.combinations_with_replacement(range(1, m + 1), n))
max = 0
for i in range(len(ff)):
  s = 0
  for j in range(q):
    a,b,c,d = num_list[j]
    if ff[i][b-1] - ff[i][a-1] == c:
      s = s + d
  if max < s:
        max = s
print(max)

Submission status: Accepted

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

from itertools import combinations_with_replacement as com
ans = 0
for A in com(range(1, M+1), N):
    score = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            score += d
    if ans < score:
        ans = score
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())
import itertools
ans = 0
for seq in itertools.combinations_with_replacement(range(1,M+1),N):
    score = 0
    for i in range(Q):
        if seq[b[i]-1] - seq[a[i]-1] == c[i]:
            score += d[i]
    ans = max(ans,score)
print(ans)

Submission status: Accepted

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

reqs = sorted(reqs, key=lambda x: x[1])

def search(A, req_head):
    if req_head >= len(reqs):
        return 0

    max_score = 0
    for e in range(A[-1], M+1):
        score = 0
        i = req_head
        while i < len(reqs) and reqs[i][1] < len(A):
            i += 1
        while i < len(reqs) and reqs[i][1] == len(A):
            a, b, c, d = reqs[i]
            if e - A[a] == c:
                score += d
            i += 1
        score += search(A + [e], i)
        max_score = max(max_score, score)

    return max_score

print(search([None, 1], 0))

Submission status: Accepted

Solution code:
import itertools
n,m,q=list(map(int,input().split()))
q_l=[list(map(int,input().split())) for _ in range(q)]
#bar_l = [(i,j,k) for i in range(0,m+1) for j in range(i,m+1) for k in range(j,m+1)]
bar_m = [i for i in range(m)]
bar_l = list(itertools.combinations_with_replacement(bar_m,n))
score = 0
for bar in bar_l:
    score_tmp=0
    for queue in q_l:
        if bar[queue[1]-1]-bar[queue[0]-1]==queue[2]:
            score_tmp+=queue[3]
    #print(score_tmp)
    if score<=score_tmp:
        score=score_tmp
        #print(bar)
print(score)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split(" "))
rule_list = []
for i in range(Q):
        rule_list.append(list(map(int,input().split(" "))))
basic_list = [0]*N
pattern_list = [basic_list]
def mklist(temp,temp2):
    global pattern_list
    global basic_list
    if temp>0:
        for j in range(temp2,N):
            basic_list[j] +=1
            pattern_list.append([*basic_list])
            mklist(temp-1,j)
            basic_list[j] -=1

temp = M-1
mklist(temp,0)
max_d = 0
for i in pattern_list:
    sum_d = 0
    for j in rule_list:
        a = j[0]
        b = j[1]
        c = j[2]
        d = j[3]
        dis = 0
        for k in range(a-1,b-1):
            dis += i[k]
        if dis == c:
            sum_d += d
    max_d = max(max_d,sum_d)
print(max_d)

Submission status: Accepted

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

n,m,q = map(int,input().split())
seq = list(range(n+m-1))
p = list(itertools.combinations(seq,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())

res = 0
for i in range(len(p)):
    t = [0]*n
    pp = sorted(p[i])
    idx = 0
    for e in pp:
        t[idx] = 1+e-idx
        idx += 1
    
    tmp = 0
    for j in range(q):
        if t[b[j]-1] - t[a[j]-1] == c[j]:
            tmp += d[j]
    
    res = max(res,tmp)

print(res)

Submission status: Accepted

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

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

if n == 2:
    for i1 in range(1, m + 1):
        for i2 in range(i1, m + 1):
            l = [i1, i2]
            v = 0
            for j in x:
                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                    v += j[3]
            ans = max(ans, v)
elif n == 3:
    for i1 in range(1, m + 1):
        for i2 in range(i1, m + 1):
            for i3 in range(i2, m + 1):
                l = [i1, i2, i3]
                v = 0
                for j in x:
                    if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                        v += j[3]
                ans = max(ans, v)
elif n == 4:
    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):
                    l = [i1, i2, i3, i4]
                    v = 0
                    for j in x:
                        if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                            v += j[3]
                    ans = max(ans, v)
elif n == 5:
    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):
                        l = [i1, i2, i3, i4, i5]
                        v = 0
                        for j in x:
                            if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                v += j[3]
                        ans = max(ans, v)
elif n == 6:
    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):
                            l = [i1, i2, i3, i4, i5, i6]
                            v = 0
                            for j in x:
                                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                    v += j[3]
                            ans = max(ans, v)
elif n == 7:
    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):
                                l = [i1, i2, i3, i4, i5, i6, i7]
                                v = 0
                                for j in x:
                                    if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                        v += j[3]
                                ans = max(ans, v)
elif n == 8:
    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):
                                    l = [i1, i2, i3, i4, i5, i6, i7, i8]
                                    v = 0
                                    for j in x:
                                        if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                            v += j[3]
                                    ans = max(ans, v)
elif n == 9:
    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):
                                        l = [i1, i2, i3, i4, i5, i6, i7, i8, i9]
                                        v = 0
                                        for j in x:
                                            if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                                v += j[3]
                                        ans = max(ans, v)
else:
    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):
                                            l = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                            v = 0
                                            for j in x:
                                                if l[j[1] - 1] - l[j[0] - 1] == j[2]:
                                                    v += j[3]
                                            ans = max(ans, v)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for seq in itertools.combinations_with_replacement(range(1, n_max+1), n_len):
    point_tmp = 0
    for a, b, c, d in qs:
        if(seq[b-1]-seq[a-1] == c):
            point_tmp += d
            # print(seq, b-1, a-1, c, ans)
    ans = max(ans, point_tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
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.append(_a-1)
    b.append(_b-1)
    c.append(_c)
    d.append(_d)
ans = 0

for A in combinations_with_replacement(range(1, M+1), r=N):
    dmax = 0
    for q in range(Q):
        if A[b[q]] - A[a[q]] == c[q]:
            dmax += d[q]
    ans = max(ans, dmax)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations_with_replacement


def get_result(data):
    N, M, Q = data[0]
    cond = data[1:]
    seq = [i+1 for i in range(M)]
    all_seq = combinations_with_replacement(seq, N)
    scores = []
    for seq in all_seq:
        score = 0
        for c in cond:
            if (seq[c[1]-1] - seq[c[0]-1]) == c[2]:
                score += c[3]
        scores.append(score)
    return max(scores)


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
import itertools
 
N,M,Q=map(int,input().split())
all=[]
for i in range(Q):
  all.append(list(map(int,input().split())))
 
x=[i for i in range(1,M+1)]
maxdsum=0
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

for i in range(Q):
  a = list(map(int,input().split()))
  List.append(a)
  
ans = 0

for team in itertools.combinations_with_replacement(range(1,M+1), N):
  cnt = 0
  for i in range(Q):
    a = List[i][0]
    b = List[i][1]
    c = List[i][2]
    d = List[i][3]
    
    if team[b-1] - team[a-1] == c:
      cnt += d
  ans = max(ans ,cnt)  
  
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import combinations_with_replacement

n, m, q = na()
abcd = nan(q)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

ans = 0


def dfs(cur, l):
    global ans
    if len(l) == N:
        s = 0
        for cond in conds:
            a, b, c, d = cond
            if l[b] - l[a] == c:
                s += d
        ans = max(ans, s)
        return

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


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations_with_replacement
def main():
    N, M, Q = map(int, input().split())
    q_list = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        q_list.append((a, b, c, d))
    A = combinations_with_replacement(range(1, M+1), N)
    ans = 0
    for Ai in A:
        v = 0
        Ai = list(map(int, Ai))
        for a, b, c, d in q_list:
            if Ai[b-1]-Ai[a-1] == c:v += d
        ans = max(ans, v)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
import copy
import sys

rl = sys.stdin.readline

n,m,q=map(int,rl().split())
x=[list(map(int,rl().split())) for i in range(q)]
#x.sort(key=lambda x:x[3],reverse=True)

def calc(lst):
  sum=0
  #print(lst)
  for a,b,c,d in x:
    if(lst[b]-lst[a]==c):
      sum+=d
      #print(a,b,c,d,sum)
  return sum
      
def dfs(n,lst,i):
  ans=0
  lst.append(i)
  if(n==0):
    ans=calc(lst)
  else:
    for j in range(i,m+1):
      tmp=copy.copy(lst)
      ans=max(ans,dfs(n-1,tmp,j))
  return ans

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

Submission status: Accepted

Solution code:
import itertools

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

max_score = 0

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

print(max_score)

Submission status: Accepted

Solution code:
import itertools

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

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

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

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cmb

N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
s = 0

for _ in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

for A in cmb(range(1,M+1),N):
    _s = 0
    for q in range(Q):
        if A[b[q]-1] - A[a[q]-1] == c[q]:
            _s += d[q]
    
    s = max(s,_s)

print(s)

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

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

Submission status: Accepted

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


ans=0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
    A=sorted(A)
    total=0
    for k in range(Q):
        if A[(S[k][1]-1)]-A[S[k][0]-1]==S[k][2]:
            total+=S[k][3]
    if total>ans:
        ans=total

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combinations
n,m,q = map(int,input().split())
r = tuple(range(1,m+1))
l = [tuple(map(int,input().split())) for i in range(q)]
ans = 0
for a in combinations(r,n):
    x=0
    for t in l:
        if a[t[1]-1]-a[t[0]-1]==t[2]:
            x+=t[3]
    ans=max(ans,x)
print(ans)

Submission status: Accepted

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

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

ans = 0
def dfs(A):
  global ans
  if len(A) == N:
    ans = max(ans, calc_score(A))
  else:
    last_a = A[-1]
    for a in range(last_a, M+1):
      dfs(A + [a])

dfs([1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    # dict = {}
    # for i in range(Q):
    #     if not c[i] in dict:
    #         dict[c[i]] = 0
    #     dict[c[i]] += d[i]
    # m = 0
    # C = -1
    # for i in dict.items():
    #     m = max(m, i[1])
    # for i in dict.items():
    #     if i[1] == m:
    #         C = i[0]
    # s = 0
    # for i in range(1, M + 1):
    #     for j in range(1, M + 1):
    #         for k in range(Q):
    #             if j - i == C or i - j == C:
    #                 if i == a[k] and j == b[k]:
    #                     s += d[k]
    # print(s)
    ts = itertools.combinations_with_replacement(range(1, M + 1), N)
    m = 0
    for t in ts:
        s = 0
        for i in range(Q):
            if t[b[i] - 1] - t[a[i] - 1] == c[i]:
                s += d[i]
        m = max(m, s)
    print(m)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


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

ans = 0
for now in A:
    point = 0
    for a, b, c, d in abcd:
        if now[b-1] - now[a-1] == c:
            point += d

    ans = max(ans, point)

print(ans)