Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
N,M,Q = map(int, input().split())
 
arr=[list(map(int,input().split())) for _ in range(Q)]
 
# Aの数列を作る。長さがMAX=Nだからとりあえず全探索
 
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:
from collections import deque


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

    seqs = deque([])
    ids = deque([N - 1] * M)
    for i in range(M):
        seqs.append([1] * (N - 1) + [i + 1])

    ans = 0
    while seqs:
        seq, idx = seqs.popleft(), ids.popleft()
        # calc score
        score = 0
        for a, b, c, d in q:
            if seq[b] - seq[a] == c:
                score += d
        ans = max(ans, score)
        # push new sequence
        if idx == 0:
            continue
        for i in range(1, seq[idx] + 1):
            seqs.append(seq[:idx - 1] + [i] + seq[idx:])
            ids.append(idx - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(nums, length, min_lim):
# 返り値は、すべての数列の得点の最大値 ans です。
# numsは数列の本体、lengthは数字の何個目まで決めたか、min_limは次の数字の最小値
    ans = 0
    if length == n:
    # 数列が完成したので、得点を計算します
        score_ret = 0
        for a, b, c, d in req:
            # nums[0]を捨てたので、nums[b-1]...としなくて済みます
            if nums[b] - nums[a] == c:  
                score_ret += d
        return score_ret  # この数列の得点を返します
    else:
        # まだ数列が完成していません
        for nu in range(min_lim, m + 1):
        # 次の数字の下限はmin_limで、上限はmです
            new_nums = nums + [nu]  # 長さ1のリスト[nu]を連結します
            # lengthは1増えて、次の下限は今付け加えた数字nuです
            score = dfs(new_nums, length + 1, nu)
            ans = max(ans, score) # 最大の得点を更新します

    # すべてが終わったので、答えを返します
    return ans


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

# 問題文のa,b,c,dの「リストのリスト」reqです。[[a1,b1,c1,d1],[a2,b2,c2,d2],[a3,b3,c3,d3]]のようになります。
req = [list(map(int, input().split())) for _ in range(q)]

# 最終的に答えが返ってくるようにします。処理はすべてdfsメソッドでやってもらいます。
# 数列の番号と添字を一致させたいので、適当な長さ1のリストを最初の状態にしておきます。
# 例えばサンプル1の1,3,4は[-1, 1, 3, 4]になります。
ans = dfs([-1], 0, 1)
print(ans)

Submission status: Accepted

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

aaa = []
for i in range(1, m+1):
    aaa.append(i)
l = []
for i in range(q):
    a = list(map(int, input().split()))
    l.append(a)
    
a = list(combinations_with_replacement(aaa, n))
ans = 0

for i in a:
    aa = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            aa+=j[3]
        if aa > ans:
            ans = aa
print(ans)

Submission status: Accepted

Solution code:
import copy

def dfs(a, b, c, d, A, N, M, Q):
    ans = 0
    if len(A) == 0:
        s = 1
    else:
        s = A[-1]
    A.append(0)
    if len(A) == N:
        for v in range(s, M+1):
            A[-1] = v
            ans_q = 0
            for q in range(Q):
                if (A[b[q]] - A[a[q]]) == c[q]:
                    ans_q += d[q]
            ans = max(ans_q, ans)
    else:
        for v in range(s, M+1):
            A[-1] = v
            ans = max(dfs(a, b, c, d, copy.copy(A), N, M, Q), ans)
    return ans

N, M, Q = [int(a) for a in input().split()]
a = []
b = []
c = []
d = []
A = []

for q in range(Q):
    in_ = [int(a) for a in input().split()]
    a.append(in_[0]-1)
    b.append(in_[1]-1)
    c.append(in_[2])
    d.append(in_[3])

ans = dfs(a,b,c,d,A,N,M,Q)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M ,Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for a,b,c,d in abcd:
            if A[b-1] - A[a-1] == c:
                score += d
        ans = max(ans, score)
    else:
        for i in range(A[-1], M+1):
            dfs(A + [i])

for j in range(1, M+1):
    dfs([j])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M ,Q = map(int, input().split())
abcd = [0 for _ in range(Q)]
for i in range(Q):
    abcd[i] = list(map(int, input().split()))

ans = 0
def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for i in range(Q):
            if A[abcd[i][1]-1] - A[abcd[i][0]-1] == abcd[i][2]:
                score += abcd[i][3]
        ans = max(ans, score)
    else:
        for i in range(A[-1], M+1):
            dfs(A + [i])

for j in range(1, M+1):
    dfs([j])
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
def main():
    n,m,q=map(int,input().split())
    Se=[]
    for i in range(q):
        Se.append(tuple(map(int,input().split())))
    #print(Se)
    integerset={i for i in range(1,m+1)}
    #print(integerset)
    everyset=itertools.combinations_with_replacement(integerset,n)
    max=0
    for v in everyset:
    #  print(v)
    #   print(len(v))
        sum=0
        for i in range(len(Se)):
            if v[Se[i][1]-1]-v[Se[i][0]-1]==Se[i][2]:
                sum+=Se[i][3]
    # print(sum)
        if sum>max:
            max=sum
    print(max)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
Se=[]
for i in range(q):
    Se.append(tuple(map(int,input().split())))
#print(Se)
integerset={i for i in range(1,m+1)}
#print(integerset)
everyset=itertools.combinations_with_replacement(integerset,n)
max=0
for v in everyset:
  #  print(v)
 #   print(len(v))
    sum=0
    for i in range(len(Se)):
        if v[Se[i][1]-1]-v[Se[i][0]-1]==Se[i][2]:
            sum+=Se[i][3]
   # print(sum)
    if sum>max:
        max=sum
print(max)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
Se=[]
for i in range(q):
    Se.append(list(map(int,input().split())))
#print(Se)
integerset={i for i in range(1,m+1)}
#print(integerset)
everyset=itertools.combinations_with_replacement(integerset,n)
max=0
for v in everyset:
  #  print(v)
 #   print(len(v))
    sum=0
    for i in range(len(Se)):
        if v[Se[i][1]-1]-v[Se[i][0]-1]==Se[i][2]:
            sum+=Se[i][3]
   # print(sum)
    if sum>max:
        max=sum
print(max)

Submission status: Accepted

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

def dfs(array, length, next_min):
    ans = 0
    if length == n:
        score = 0
        for a,b,c,d in req:
            if array[b-1] - array[a-1] == c:
                score += d
        
        return score
    
    else:
        for num in range(next_min, m+1):
            next_array = array + [num]
            ans = max(dfs(next_array, length+1, num), ans)
    
    return ans

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

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
vec = [list(map(int, input().split())) for i in range(Q)]
A = itertools.combinations_with_replacement(range(1,M+1), N)
ans = 0

for a in A:
    tmp = 0
    for v in vec:
        if (a[v[1]-1] - a[v[0]-1]) == v[2]:
            tmp += v[3]
    if ans < tmp:
        ans = tmp
        
print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
from itertools import combinations_with_replacement
a=[i for i in range(1,M+1)]
A=list(combinations_with_replacement(a,N))
#print(A)
ans=[]
for i in range(Q):
    W,X,Y,Z=map(int,input().split())
    #print(X,W)
    for j in A:
        if j[X-1]-j[W-1]==Y:
            ans.append(Z)
        else:
            ans.append(0)
#print(ans)
C=len(A)
Ans=[]

for i in range(C):
    tmp=0
    F=ans[i::C]
    tmp=sum(F)
    Ans.append(tmp)
#print(Ans)
print(max(Ans))

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0

for A in itertools.combinations_with_replacement(range(1, m+1), n):
    res = 0
    for i in range(q):
        if A[l[i][1]] - A[l[i][0]] == l[i][2]:
            res += l[i][3]
    ans = max(ans, res)

print(ans)

Submission status: Accepted

Solution code:
def dfs(i, A):
    global res
    global ans
    if len(A) == n:
        res = 0
        for j in range(q):
            if A[l[j][1]] - A[l[j][0]] == l[j][2]:
                res += l[j][3]
        ans = max(ans, res)
        return ans
    lim = 1
    lim = 1 if i == 0 else A[i-1]
    for k in range(lim, m+1):
        A.append(k)
        dfs(i+1, A)
        A.pop()
        
n, m, q = map(int, input().split())
A = []
l = []
ans = 0

for i in range(q):
    a, b, c, d = map(int, input().split())
    l.append([a-1, b-1, c, d])
dfs(0, A)
print(ans)

Submission status: Accepted

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


def dfs(i, A):
    global ans
    if i == n:
        res = 0
        for j in range(q):
            if A[l[j][1]] - A[l[j][0]] == l[j][2]:
                res += l[j][3]
        return res
    lim = 1
    lim = 1 if i == 0 else A[i-1]
    for k in range(lim, m+1):
        A[i] = k
        ans = max(ans, dfs(i+1, A))
    return ans

A = [0] * n
l = []
ans = 0

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

print(dfs(0, A))

Submission status: Accepted

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

def create(N,M):
    S = [[] for _ in range(N+1)]
    for m in range(1,M+1):
        S[1].append([m])
    for n in range(1,N):
        for s in S[n]:
            Max = s[-1]
            for i in range(Max, M+1):
                S[n+1].append(s+[i])
    return S

highest = 0
for letters in create(N,M)[N]:
    point = 0
    for a,b,c,d in pattern_list:
        if c == letters[b-1]-letters[a-1]:
            point += d
    highest = max([highest, point])

print(highest)

Submission status: Accepted

Solution code:
# 重複組み合わせの全列挙

import itertools

# n+m-1個からn個を選ぶ組み合わせ
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 p:
    t = [0] * n
    idx = 0
    for e in i:
        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 itertools

# n+m-1個からn個を選ぶ組み合わせ
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 p:
    t = [0] * n
    pp = sorted(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 itertools

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:
N,M,Q = [int(x) for x in input().split()]
A,B,C,D =[],[],[],[]
for _ in range(Q):
    a,b,c,d = [int(x) for x in input().split()]
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

def calc(T):
    score = 0
    for i in range(Q):
        if T[B[i]-1] - T[A[i]-1] == C[i]:
            score += D[i]
    return score

MA = 0
def dfs(T):
    global MA
    if len(T) == N:
        # print(T, calc(T))
        MA = max(MA, calc(T))
        return
    
    mi = 1 if len(T) == 0 else T[-1]
    for i in range(mi, M+1):
        T.append(i)
        dfs(T)
        T.pop()

dfs([])
print(MA)

Submission status: Accepted

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

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

# Aの数列を作る。長さがMAX=Nだからとりあえず全探索

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 itertools

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

ABCD=[]

max_result=0

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

for j in itertools.combinations([k for k in range(M+N-1)],N):
    result=0
    for l in ABCD:
        if  j[l[1]-1]-j[l[0]-1]==l[1]-l[0]+l[2]:
            result+=l[3]
    
    if result>max_result:
        max_result=result

print(max_result)

Submission status: Accepted

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

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

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

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

def s(A):
    if A[len(A) - 1] > m or len(A) > n:
        return 0
    elif len(A) == n:
        ans = 0
        for i in range(q):
            if (A[b[i] - 1] - A[a[i] - 1] == c[i]):
                ans += d[i]
        #print(A)
        #print(ans)
        return ans
    else:
        max_ans = 0
        for i in range(A[len(A) - 1], m + 1):
            tA = list(A)
            tA.append(i)
            max_ans = max(max_ans, s(tA))
        return max_ans

T = [1]
print(s(T))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def generator(n, r):
    if r == 0:
        yield []
    else:
        a = 0
        for A in generator(n, r - 1):
            if r > 1:
                a = A[-1]
            for i in range(a, n):
                A.append(i)
                yield A
                A.pop()


n, m, q = map(int, input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
for X in generator(m, n):
    scr = 0
    for a, b, c, d in ABCD:
        if X[b - 1] - X[a - 1] == c:
            scr += d
    ans = max(ans, scr)
print(ans)

Submission status: Accepted

Solution code:
def search(v, n, m, seq, scs):
    if len(seq) == n:
        ans = 0
        for r in scs:
            if seq[r[1]-1] - seq[r[0]-1] == r[2]:
                ans += r[3]
        return ans
    ans = 0
    for i in range(v, m+1):
        tmp = search(i, n, m, seq + [i], scs)
        ans = max(ans, tmp)
    return ans

def resolve():
    n, m, q = map(int, input().split())
    scs = [list(map(int, input().split())) for _ in range(q)]
    v = search(1, n, m, [], scs)
    print(v)
resolve()

Submission status: Accepted

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

def score(A):
    s = 0
    for i in range(q):
        a = l[i][0]
        b = l[i][1]
        c = l[i][2]
        d = l[i][3]
        if A[b-1] - A[a-1] == c:
            s += d
    return s
        
ans = 0

def dfs(A):  #Aはリスト
    global ans
    if len(A) == n:
        t = score(A)
        ans = max(ans, t)
        return
    
    
    if len(A)>0:
        lastn = A[-1]
    else:
        lastn =1
        
    for i in range(lastn, m+1):
        A.append(i)
        dfs(A)
        A.pop()
    

dfs([])
print(ans)

Submission status: Accepted

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


#最初に全てのAペアを作ればいいだけだった
#1stepで何するか
#終了条件
ans = [0]
def dfs(A):
    # print(A)
    if len(A) == N:
        tmp_ans = 0
        for ele in tmp:
            if A[ele[1]-1] - A[ele[0]-1] == ele[2]:
                tmp_ans += ele[-1]
        ans[0] = max(tmp_ans,ans[0])

        return
    
    A_min = A[-1]
    while(1):
        if A_min > M:
            break
        A.append(A_min)
        dfs(A)
        A.pop()
        A_min += 1

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

print(ans[0])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

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


def calc(A):
    if len(A) == N:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tmp += d
        global ans
        ans = max(ans, tmp)
    else:
        for i in range(A[-1], M + 1):
            calc(A + [i])


def solve():
    for i in range(1, M + 1):
        calc([i])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


V = [[] for _ in range(N+1)]

# 初期値として長さ1のものを入れる
for i in range(1, M+1):
    V[1].append([i])

# V[k] から V[k+1] を作る
for i in range(1, N):
    for v in V[i]:
        # 単調増加なので、末尾の値以上であるものを全て試す
        b = v[-1]
        for a in range(b, M+1):
            v2 = v + [a]
            V[i+1].append(v2)
#print(V)
maxi=0
for w in V[N]:
    total=0
    for i in s:
        if w[i[1]-1]-w[i[0]-1]==i[2]:
            total+=i[3]
        if maxi<total:
            maxi=total
        #print(i)
print(maxi)

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
 
N, M, Q = map(int, input().split())
input_lst = [list(map(int, input().split())) for _ in range(Q)]
 
max_score = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    score = 0
    for row in input_lst:
        a, b, c, d = row
        if pattern[b - 1] - pattern[a - 1] == c:
            score += d
    if score > max_score:
        max_score = score
print(max_score)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = [int(i) for i in input().split()]
a = []
for _ in range(Q):
    a.append([int(i) for i in input().split()])
ans = 0
for L in itertools.combinations_with_replacement(range(1,M+1), N):
    s = 0
    for i in range(Q):
        if L[a[i][1]-1]-L[a[i][0]-1] == a[i][2]:
            s += a[i][3]
    ans = max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb
N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(Q)]
ans = 0
for lista in comb([j for j in range(1,M+1)],N):
    lista=list(lista)
    ansi = 0
    for a,b,c,d in abcd:
        if lista[b-1]-lista[a-1]==c:
            ansi+=d
    ans = max(ans,ansi)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb
N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(Q)]
ans = 0
lista = [list(i) for i in comb([j for j in range(1,M+1)],N)]
for lis in lista:
    ansi = 0
    for a,b,c,d in abcd:
        if lis[b-1]-lis[a-1]==c:
            ansi+=d
    ans = max(ans,ansi)
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)]
ans = 0
def dfs(n,A,now):
    global ans
    if n == 0:
        ansi = 0
        for a,b,c,d in abcd:
            if A[b-1]-A[a-1]==c:
                ansi+=d
        ans = max(ans,ansi)
    else:
        for i in range(now,M+1):
            dfs(n-1,A+[i],i)

A = []
dfs(N,A,1)
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)]
ans = 0
for a in range(1,M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    for j in range(i,M+1):
                                        lista = [a,b,c,d,e,f,g,h,i,j]
                                        ans1 = 0
                                        for A,B,C,D in abcd:
                                            if lista[B-1]-lista[A-1] == C:
                                                ans1 += D
                                        ans = max(ans,ans1)
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]-=1
    b[i]-=1
def score(A):
    tmp=0
    for ai,bi,ci,di in zip(a,b,c,d):
        if A[bi]-A[ai] == ci:
            tmp+=di
    return tmp


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

print(dfs([]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(A):
        res = 0
        for a,b,c,d in g:
            if A[b] == A[a]+c:
                res += d
        return res
    N,M,Q = map(int,input().split())
    g = [list(map(int,input().split())) for i in range(Q)]
    #g[i][0] == ai
    for i in range(Q):
        g[i][0] -= 1  #ai -= 1
        g[i][1] -= 1  #bi -= 1
    l = [([i],i) for i in range(1,M+1)]  #[([1],1),([2],2),....,([M],M)]
    for i in range(N-1): #1個目の要素にN桁の数列を生成
        l = [(x+[j], j) for (x,y) in l for j in range(y,M+1)]
    ans = 0
    for A,_ in l:
        s = f(A)
        if ans < s:
            ans = s #得点の最大値を厳選
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

A_cands = np.array(list(itertools.combinations_with_replacement(list(range(1, M+1)), N)))      

scores = np.zeros(len(A_cands), dtype=np.int64)

for i in range(Q):
    a, b, c, d = G[i]
    cond = A_cands[:, b - 1] - A_cands[:, a - 1] == c
    scores += cond * d
print(scores.max())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
import itertools

def main():
    length_of_sequence,maximum_value,number_of_query = map(int,input().split())
    
    sequences =  [ next_sequence+1 for next_sequence in range(maximum_value)]
    
    sequences_list = [sequence for sequence in itertools.combinations_with_replacement(sequences,length_of_sequence) if all([item <= sequence[item_suffix+1] for item_suffix,item in enumerate(sequence) if item_suffix < len(sequence) - 1])]
    
    query_information_list = []
    for query_number in range(number_of_query):
        query_information = list(map(int,input().split()))
        query_information_list.append(query_information)
    query_information_list = sorted(query_information_list,key=lambda x:x[3],reverse=True)
    result_list = []
    for sequences in sequences_list:
        result_list.append(sum([item[3] for item in query_information_list if sequences[item[1]-1] -  sequences[item[0]-1] == item[2]]))
    
    if result_list:
        print(max(result_list))
    else:
        print(0)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for cand in A_cands:
    cand_score = 0
    for i in range(Q):
        a, b, c, d = G[i]
        if cand[b - 1] - cand[a - 1] == c:
            cand_score += d
    ans = max(cand_score, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, q = map(int, readline().split())

a = [0 for i in range(50)]
b = [0 for i in range(50)]
c = [0 for i in range(50)]
d = [0 for i in range(50)]

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


A = [0 for i in range(n)]
A[0] = 1

ans = 0
def dfs(length):
    if length == n:
        #process
        # print(A)
        total = 0
        global ans
        for i in range(q):
            if A[b[i] - 1] - A[a[i] - 1] == c[i]:
                total += d[i]
        ans = max(total, ans)
        return

    lastItem = A[length - 1]
    while lastItem <= m:
        A[length] = lastItem
        dfs(length + 1)
        lastItem += 1
dfs(1)
print(ans)

Submission status: Accepted

Solution code:
import copy

def dfs(ar, num, cnt):
  ar.append(num)
  if cnt < n-1:
    ans = 0
    for i in range(num, m+1):
      rep = dfs(copy.deepcopy(ar), i, cnt+1)
      ans = max([ans, rep])
    return ans
  else:
    ans = 0
    for i in range(q):
      if ar[abcd[i][1]-1] - ar[abcd[i][0]-1] == abcd[i][2]:
        ans += abcd[i][3]
    return ans

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

ans = 0
for i in range(1,m+1):
  a = []
  rep = dfs(copy.deepcopy(a), i, 0)
  ans = max([ans, rep])
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

import itertools


for con in itertools.combinations_with_replacement(range(1,m+1),n):
    tmpAns = 0
    for lst in arr:
        if con[lst[1]-1] - con[lst[0]-1] == lst[2]:
            tmpAns += lst[3]
    ans = max(ans, tmpAns)

print(ans)

Submission status: Accepted

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

lst = []
def generate(l):
    global lst, n, m
    if len(l) == n:
        lst.append(l)
        return 0
    if l == []:
        for i in range(1,m+1):
            generate([i])
        return 0
    for i in range(l[-1], m+1):
        t = l + [i]
        generate(t)

generate(lst)    

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
X = []
for i in range(0, Q):
    X.append(list(map(int, input().split())))
sample = list(combinations_with_replacement(range(1, M+1), N))
ans = 0
for s in sample:
    tmp = 0
    for x in X:
        if s[x[1]-1]-s[x[0]-1] == x[2]:
            tmp += x[3]
    ans = max(tmp, ans)
print(ans)