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

result = 0
max = 0
for A in combinations_with_replacement(range(1, m+1), n):
    for i in range(q):
        a, b, c, d = abcd[i]
        if A[b-1] - A[a-1] == c:
            result += d
    if result > max:
        max = result
        reslut = 0
    result = 0

print(max)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwp
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)
ans=0
for t in cwp(range(1,M+1),N):
    now=0
    for i in range(Q):
        if t[B[i]-1]-t[A[i]-1]==C[i]:
            now+=D[i]
    ans=max(now, ans)
print(ans)

Submission status: Accepted

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

Q_list = [[0 for i in range(4)] for j in range(Q)]
for i in range(Q):
    Q_list[i] = list(map(int, input().split()))


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
                                        A_list = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        for a,b,c,d in Q_list:
                                            if A_list[b]-A_list[a]==c:
                                                tmp+=d
                                        ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
# Problem C - Many Requirements

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

# initialization
ans_score = 0
num_list = []

# calc func
def dfs(num_list, keta, c):
    global ans_score
    global N
    if keta==N:
        # check
        tmp = 0
        for r in rules:
            if num_list[r[1]-1]-num_list[r[0]-1]==r[2]:
                tmp += r[3]
        ans_score = max(ans_score, tmp)
        return

    for n in range(c, M+1):
        num_list.append(n)
        dfs(num_list, keta+1, n)
        num_list.pop(-1)

# calc
dfs(num_list, 0, 1)

# output
print(ans_score)

Submission status: Accepted

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

combi = list(range(M))

test = list(combinations_with_replacement(combi,N))

ans = 0

for i in test:
    sum = 0
    for j in range(Q):
        if i[listh[j][1]-1] - i[listh[j][0]-1] == listh[j][2]:
            sum += listh[j][3]
    if(sum > ans):
        ans = sum

print(ans)

Submission status: Accepted

Solution code:
import copy
N, M, Q = list(map(int, input().split()))
Qs = [[0] * 4 for i in range(Q)]
for i in range(Q):
    Qs[i][0], Qs[i][1], Qs[i][2], Qs[i][3] = list(map(int, input().split()))
ans = -1

# 再帰で全探索
# 後ろから<=Mまで順番に1増加させることで、それぞれ<=Mの広義単調増加の全探索ができる
def dfs(A):
    global ans
    if len(A) == N + 1:
        sum_ = 0
        for i in range(Q):
            if A[Qs[i][1]] - A[Qs[i][0]] == Qs[i][2]:
                sum_ += Qs[i][3]
        ans = max(ans, sum_)
        return
        
    A.append(A[-1])
    while (A[-1] <= M):
        dfs(copy.copy(A))
        A[-1] += 1
    return

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
def bfs(n, m, v):
    if n == 0:
        return f(v)
    return max(f(bfs(n-1, x, [x]+v)) for x in range(1, m+1))

def solve(n, m, q, a, b, c, d):
    def f(v):
        return sum(d[i] for i in range(q) if v[b[i]-1] - v[a[i]-1] == c[i])
    def bfs(n, m, v):
        if n == 0:
            return f(v)
        return max(bfs(n-1, x, [x]+v) for x in range(1, m+1))
    return bfs(n, m, [])

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())
print(solve(n, m, q, a, b, c, d))

Submission status: Accepted

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

nums = list(range(1, m+1))
ans = 0
for i in combinations_with_replacement(nums, n):
  t = 0
  for j in abcd:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      t += j[3]
  ans = max(ans, t)
print(ans)

Submission status: Accepted

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

X = []
ans = 0

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

def search():
    global ans

    if len(X) == N:
        ans = max(ans, calc())
        return

    for i in range(X[-1], M + 1):
        X.append(i)
        search()
        X.pop()

    return

for i in range(1, M + 1):
    X.append(i)
    search()
    X.pop()

print(ans)

Submission status: Accepted

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

As = []
q = [[]]
while len(q) > 0:
    arg = q.pop()
    if len(arg) == N:
        As.append(arg)
    else:
        A_str = 1 if len(arg) == 0 else arg[-1]
        for i in range(A_str, M + 1):
            q.append(arg + [i])

ans = 0
for A in As:
    ans_tmp = 0
    for j, (aj, bj, cj, dj) in enumerate(abcd):
        if A[bj - 1] - A[aj - 1] == cj:
            ans_tmp += dj
    #
    ans = max(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product,combinations
N,M,Q = map(int,input().split())
B = [list(map(int,input().split())) for _ in range(Q)]
ans = 0
for x in product((0,1),repeat=N-1):
    k = sum(x)
    for y in combinations(range(1,M+1),k+1):
        A = [0 for _ in range(N)]
        cur = 0
        for i in range(N-1):
            if x[i]==0:
                A[i] = y[cur]
            else:
                A[i] = y[cur]
                cur += 1
        A[N-1] = y[cur]
        cnt = 0
        for i in range(Q):
            a,b,c,d = B[i]
            if A[b-1]-A[a-1]==c:
                cnt += d
        ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int,input().split())
L = [k+1 for k in range(M)]
S = [list(map(int,input().split())) for _ in range(Q)]
ans = 0
for e in itertools.combinations_with_replacement(L,N):
    temp = 0
    for f in S:
        a, b, c, d = f[0]-1, f[1]-1, f[2], f[3]
        if e[b]-e[a] == c:
            temp += d
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    abcd = [tuple(map(int, input().split())) for _ in range(Q)]
    stk = [[]]
    ans = 0
    while stk:
        A = stk.pop()
        if len(A) < N:
            t = A[-1] if len(A) > 0 else 0
            for i in range(t, M):
                stk.append(A + [i])
        else:
            t = 0
            for a, b, c, d in abcd:
                if A[b - 1] - A[a - 1] == c:
                    t += d
            ans = max(ans, t)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import itertools

n, m, q = [int(x) for x in input().split()]
abcd = []
for _ in range(q):
    abcd.append([int(x) for x in input().split()])
ele = [int(x) for x in range(1, m + 1)]
p = list(itertools.combinations_with_replacement(ele, n))
ans = -1
for i in range(len(p)):
    p_ = p[i]
    res = 0
    for j in range(q):
        a, b, c, d = abcd[j]
        a -= 1
        b -= 1
        if p_[b] - p_[a] == c:
            res += d
    ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100)
from collections import *

def dfs(now):
    global ans
    
    if len(now)==N:
        cnt = 0
        
        for a, b, c, d in abcd:
            if now[b-1]-now[a-1]==c:
                cnt += d
        
        ans = max(ans, cnt)
        return
    
    for nex in range(now[-1], M+1):
        now.append(nex)
        dfs(now)
        now.pop()

N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

    ans = 0
    que = deque()
    que.append([])
    while que:
        now = que.popleft()
        if len(now) < n:
            minimum = (now[-1] if now else 1)
            for i in range(minimum, m+1):
                next = list(now)
                next.append(i)
                que.append(next)
        else:
            score = 0
            for x in abcd:
                if now[x[1]-1] - now[x[0]-1] == x[2]:
                    score += x[3]
            if score > ans:
                ans = score

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,q = LI()
    aa = [LI() for _ in range(q)]

    r = 0
    for t in itertools.combinations_with_replacement(range(m), n):
        u = 0
        for a,b,c,d in aa:
            if t[b-1] - t[a-1] == c:
                u += d
        if r < u:
            r = u

    return r

print(main())

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,q = [int(x) for x in input().split()]

data =[]

for _ in range(q):
    data.append([int(x) for x in input().split()])

ans = 0

def dfs(pos,prev,arr):
    global ans
    if pos == n:
        cost = 0
        for dd in data:
            a,b,c,d = dd
            if arr[b-1] - arr[a-1] == c:cost+=d
        ans = max(ans,cost)
    else:
        for i in range(prev,m+1):
            arr[pos] = i
            dfs(pos+1,arr[pos],arr)

dfs(0,1,[0]*n)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(al, n, m, all_al):
    if len(al) == n:
        all_al.append(al)
    else:
        last = al[-1]
        for i in range(last, m+1):
            dfs(al+[i], n, m, all_al)

def main():
    n, m, Q = map(int, input().split()) 
    ql = []
    for _ in range(Q):
        ql.append( list(map(int, input().split())) )

    all_al = []
    for i in range(1,m+1):
        dfs([i], n, m, all_al)

    ans = 0
    for al in all_al:
        curr_sum = 0
        for q in ql:
            if al[q[1]-1]- al[q[0]-1] == q[2]: curr_sum += q[3]
        ans = max(curr_sum, ans)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

result = 0
for A in combinations_with_replacement(range(1,M+1),N):
    t = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            t += d
    result = max(result,t)
print(result)

Submission status: Accepted

Solution code:
import itertools

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

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

A_list = []
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    A_list.append(a)

answer = 0
score_list = []
for A in A_list:
    score = 0
    for i in range(Q):
        a, b, c, d = Q_list[i]
        a -=1
        b -=1
        if A[b] - A[a] == c:
            score += d
    answer = max(answer, score)

print(answer)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = map(int, input().split())
ABCD = []
ans = 0

prob_list = itertools.combinations_with_replacement(range(1,M+1), N)

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

for prob in prob_list:
    tmp = 0
    for i in range(Q):
        a,b,c,d = ABCD[i]
        if prob[b-1] -prob[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())
ls = [list(map(int,input().split())) for i in range(Q)]

Mls = list(range(1,M+1))
Mls = [str(n) for n in Mls]
l = list(itertools.combinations_with_replacement(Mls,N))

ans = 0
for A in l:
    pnt = 0
    for l in ls:
        if int(A[l[1]-1])-int(A[l[0]-1]) == l[2]:
            pnt += l[3]
    ans = max(ans,pnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

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

Submission status: Accepted

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

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

def check_point(A,l):
    point=0
    for a in A:
        if l[a[1]-1]-l[a[0]-1] == a[2]:
            point+=a[3]

    return point

#全探索
L=[]
l=[-1]*N
d=[]
# d=0
def dfs(i,r,l):
    if r == N-1:
        for m in range(i,M):
            l[r] = m
            #処理を記述
#             print(l,check_point(A,l))
#             if d < check_point(A,l):
#                 d = check_point(A,l)
            d.append(check_point(A,l))
            L.append(l.copy())
        return 
    
    r+=1
    for m in range(i,M): 
        l[r-1] = m
        dfs(m,r,l)
        
dfs(0,0,[-1]*N)
print(max(d))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

def dfs(seq):
    if len(seq) == n:
        yield seq
        return
    if len(seq) == 0:
        _max = 1
    else:
        _max = seq[-1]
    for i in range(_max, m+1):
        new_seq = seq.copy()
        new_seq.append(i)
        yield from dfs(new_seq)

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

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
A=[]
for i  in range(q):
    A.append(list(map(int,input().split())))
ans=0
def judge(Q):
    now=0
    for l in A:
        a,b,c,d=l
        if Q[b-1]-Q[a-1]==c:
            now+=d
    global ans
    ans=max(ans,now)
    return


def dfs(L):
    if len(L)==n:
        judge(L)
        return
    jj=L[-1] if len(L)>0 else 1
    for i in range(jj,m+1):
        L.append(i)
        dfs(L)
        L.pop()

dfs([])
print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
req_ls = []
l_ind_ls = [0] * Q
r_ind_ls = [0] * Q
diff_ls = [0] * Q
point_ls = [0] * Q
for i in range(Q):
    l_ind_ls[i], r_ind_ls[i], diff_ls[i], point_ls[i] = map(int, input().split())
    l_ind_ls[i] -= 1
    r_ind_ls[i] -= 1

def score(ls):
    tmp = 0
    for l_ind, r_ind, diff, point in zip(l_ind_ls,r_ind_ls,diff_ls,point_ls):
        if ls[r_ind] - ls[l_ind] == diff:
            tmp += point
    return tmp

def dfs(ls):
    if len(ls) == N:
        return score(ls)
    res = 0
    last = ls[-1] if len(ls) > 0 else 1
    for nex in range(last, M+1):
        ls.append(nex)
        res = max(res, dfs(ls))
        ls.pop()
    return res
print(dfs([]))

Submission status: Accepted

Solution code:
import itertools

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

e = []

for i in range(q):
  e.append(list(map(int, input().split())))

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

max_total = 0

for i in a:
  total = 0
  
  for j in e:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      total += j[3]
  
  if max_total < total:
    max_total = total
      
print(max_total)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
abcd = [map(int, input().split()) for _ in range(Q)]
a, b, c, d = [list(i) for i in zip(*abcd)]

As = list(combinations_with_replacement(range(1, M+1), N))

m = -10*100

for A in As:
    sum = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            sum += d[i]
    m = max(m, sum)


print(m)

Submission status: Accepted

Solution code:
import itertools
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 itertools.combinations_with_replacement(range(M),N)))

Submission status: Accepted

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

v = []
def dfs(u,ary):
	if len(ary) == n:
		ary.sort()
		cnt = 0
		for j in range(q):
			a,b,c,d = query[j]
			if ary[b-1] - ary[a-1] == c:
				cnt += d
		v.append(cnt)
	else:
		for j in range(u,m+1):
			dfs(j,ary+[j])


dfs(1,[1])

print (max(v))

Submission status: Accepted

Solution code:
import itertools
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)
e = [i+1 for i in range(m)]
ans = 0
for i in itertools.combinations_with_replacement(e,n-1):
	f = list(i)
	f.append(1)
	f.sort()
	w = 0
	for j in range(q):
		if f[b[j]-1]-f[a[j]-1] == c[j]:
			w += d[j]
	ans = max(ans,w)
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)]
A = list(range(1, M+1))
AC = list(itertools.combinations_with_replacement(A,N))
anslist = [0] * len(AC)

for i in range(len(AC)):
  for j in range(Q):
    if AC[i][abcd[j][1]-1] - AC[i][abcd[j][0]-1] == abcd[j][2]:
      anslist[i] += abcd[j][3]

print(max(anslist))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
score_table = list(map(lambda x: [x[0]-1, x[1]-1, x[2], x[3]], [list(map(int, input().split())) for x in range(Q)]))
result = 0

for A in combinations_with_replacement(range(1,M+1), N):
    score = 0
    for i in range(Q):
        if A[score_table[i][1]] - A[score_table[i][0]] == score_table[i][2]:
            score += score_table[i][3]
            
    result = max(result, score)
    
print(result)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
all_a=[]
def make_a():
  ret=[]
  todo=[[]]
  while todo:
    i=todo.pop()
    if len(i)==n:
      ret.append(i)
      continue
    l=i[-1] if len(i)>0 else 1
    for j in range(l,m+1):
      todo.append(i+[j])
  return ret

all_a=make_a()
ans=0
for an in all_a:
  ansi=0
  for a,b,c,d in abcd:
    if an[b-1]-an[a-1]==c:
      ansi+=d
  ans=max(ans,ansi)
print(ans)

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

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

Submission status: Accepted

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

a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

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

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

  return x

def dfs(A):
  if(len(A) == n):
    return num(A)
  s = 0
  x = A[-1] if len(A) > 0 else 0
  for i in range(x, m):
    A.append(i)
    s = max(s, dfs(A))
    A.pop()

  return s
 
print(dfs([]))

Submission status: Accepted

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

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

line=[1]
ans=0

def dfs(A):
    global ans
    if len(A)==N:
        now=0
        for i in range(Q):
            if A[matrix[i][1]-1]-A[matrix[i][0]-1]==matrix[i][2]:
                now+=matrix[i][3]
        ans=max(ans,now)
        return
    A.append(A[-1])
    while(A[-1]<=M):
        dfs(copy.copy(A))
        A[-1]+=1

dfs(line)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n, m, q = map(int, input().split())
a = [0 for i in range(q)]
b = [0 for i in range(q)]
c = [0 for i in range(q)]
d = [0 for i in range(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 dfs(n, m, i, a):
    if i == n:
        global x
        x.append(a)
        return
    
    if len(a) > 0: 
        for j in range(a[-1], m + 1):
            dfs(n, m, i + 1, a + [j])
        return 
    for j in range(1, m + 1):
        dfs(n, m, i + 1, a + [j])


x = []
dfs(n, m, 0, [])
# print(x)
ans = 0
for i in x:
    cnt = 0
    for j in range(q):
        if i[b[j]] - i[a[j]] == c[j]:
            cnt += d[j]
            # print(d[j])
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

"""
# このアプローチはメモリーエラー
s=[[1]]

#長さNまで
import copy
while True:
    n = []
    for s1 in s:
        for append in range(s1[-1], M+1):
            n1 = copy.copy(s1)
            n1.append(append)
            n.append(n1)
    if len(n[0]) > M:
        break
    s = n
#for s1 in s:
#    print(s1)
iidp = [list(map(int,input().split())) for q in range(Q)]

al = 0
for s1 in s:
    a = 0
    for i1, i2, d, p in iidp:
        if s1[i2-1] - s1[i1-1] == d:
            a += p
    al = max(a,al)

print(al)
"""

iidp = [list(map(int,input().split())) for q in range(Q)]
import itertools
al = 0
for s1 in itertools.combinations_with_replacement(list(range(1,M+1)), N):
    a = 0
    for i1, i2, d, p in iidp:
        if s1[i2-1] - s1[i1-1] == d:
            a += p
    al = max(a,al)

print(al)

Submission status: Accepted

Solution code:

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

l = list(list(map(int,input().split()))for _ in range(q))
li = [x for x in range(1,m+1)]
lis  = list(itertools.combinations_with_replacement(li,n))
point = 0
for i in lis:
    p = 0
    for j in l:
        if (i[j[1]-1] - i[j[0]-1]) == j[2]:
            p += j[3] 
    point = max(p,point)
print(point)

Submission status: Accepted

Solution code:
from collections import deque
def resolve():
    def calc(seq):
        score = 0
        for a, b, c,d in query:
            if seq[b-1] - seq[a-1] == c:
                score += d
        return score


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

    q = deque()
    for i in range(1, M+1):
        q.append([i])
    ans = 0
    while q:
        seq = q.popleft()
        if len(seq) == N:
            score = calc(seq)
            ans = max(ans, score)
        else:
            for i in range(seq[-1], M+1):
                nx_seq = seq + [i]
                q.append(nx_seq)
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from numba import njit


@njit
def main(N, M, P):
    ma = 0
    for i in range(M):
        for j in range(i, M):
            for k in range(j, M):
                for l in range(k, M):
                    for m in range(l, M):
                        for n in range(m, M):
                            for o in range(n, M):
                                for p in range(o, M):
                                    for q in range(p, M):
                                        for r in range(q, M):
                                            ans = 0
                                            arr = [i, j, k, l,
                                                   m, n, o, p, q, r][:N]
                                            for a, b, c, d in P:
                                                if arr[b-1] - arr[a-1] == c:
                                                    ans += d
                                                ma = max(ma, ans)
    return ma


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

print(main(N, M, P))