Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
    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

# DFS
def dfs(A):
    if len(A) == N:
        return score(A) # 数列 A のスコアを返す
    res = 0
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        res = max(res, dfs(A)) # 再帰呼出しながら、スコア最大値も更新
        A.pop()
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
a = [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

# DFS
res = 0 # とりあえずグルーバルに置いておく
def dfs(A):
    global res # res をグルーバルで使えるように
    if len(A) == N:
        res = max(res, score(A))
        return
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])
print(res)

Submission status: Accepted

Solution code:
import itertools

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

for k in itertools.combinations_with_replacement(range(1,m+1),n):
    t=0
    for j in l:
        if k[j[1]-1]-k[j[0]-1]==j[2]:
            t+=j[3]
    
    ans=max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
def combinations_with_replacement(elements, N):
    for i, element in enumerate(elements):
        if N == 1:
            yield [element]
        else:
            for combination in combinations_with_replacement(elements[:i+1], N-1):
                combination.append(element)
                yield combination


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

ans = 0
elements = list(range(1, M+1))
for combination in combinations_with_replacement(elements, N):
    score = 0
    for i in range(Q):
        if combination[b[i]-1] - combination[a[i]-1] == c[i]:
            score += d[i]
    ans = max(score, ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m, q = map(int,input().split())
a = []
b = []
c = []
d = []
for i in range(q):
    ai, bi, ci, di = map(int,input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    tmp = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            tmp += d[i]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from string import digits

def main():
    N, M, Q = map(int, input().split())
    query = [tuple(map(int, input().split())) for _ in range(Q)]


    my_digits = list(range(1, M+1))
    r = my_digits.index(M)
    def dfs(S):
        if len(S) >= N:
            score = 0
            for a, b, c, d in query:
                if S[b-1] - S[a-1] == c:
                    score += d
            return score
        else:
            suffix = S[-1]
            l = my_digits.index(suffix)
            
            return  max([dfs(S+[num]) for num in my_digits[l:r+1]])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = 0


def dfs(A):
    global ans
    if len(A) == N:
        now = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(now, ans)
        return

    if not A:  # Aが空リストのとき
        tmp = 1
    else:
        tmp = A[-1]

    while tmp <= M:
        dfs(A + [tmp])
        tmp += 1


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

Submission status: Accepted

Solution code:
N, M,Q = map(int, input().split())
inf = []
for i in range(Q):
    a,b,c,d = map(int, input().split())
    inf.append([a,b,c,d])
"""深さ優先探索で数列を作る cren(r, progress,result) はrがループの回数、progressがそこまででできた数列
最後、resultに保存する　ラップ関数を定義して最後値を取り出す 再起的に呼び出す
for ループを再帰化する"""

def rap(n):#nこ長さの条件を満たす数列を作る
    result = []
    for i in range(1,M+1):
        progress = [i]
        cren(n-1,progress,result)
    return result

def cren(r,progress,result):
    if r == 0:
        result.append(progress)
        return
    a = progress[-1]
    for i in range(a,M+1):
        cren(r-1,progress+[i],result)
"""rapを呼び出すことで長さnの条件を満たす数列が帰ってくる　resultは記録用だからグローバル変数として
扱われるから成り立つ"""
ans = 0
ls = rap(N)
for item in ls:
    ani = 0
    for in1 in inf:
        a = in1[0]
        b = in1[1]
        if  (item[b-1] - item[a-1]) == in1[2]:
            ani += in1[3]
    ans = max(ans, ani)
print(ans)

Submission status: Accepted

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

def dfs(x):
    global ans
    if len(x) == n+1:
        t=0
        for a,b,c,d in l:
            if x[b]-x[a] == c:
                t+=d
        ans=max(ans,t)        
    else:    
        x.append(x[-1])
        while(x[-1] <= m):
            dfs(x.copy())
            x[-1] += 1
 
    
dfs([1])
print(ans)

Submission status: Accepted

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

ans  = 0
from itertools import combinations_with_replacement

for kumi in combinations_with_replacement(range(1,m+1),n):
    tmp = 0
    for ar in arr:
        if kumi[ar[1]-1]-kumi[ar[0]-1]==ar[2]:
            tmp+=ar[3]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    L = list(combinations_with_replacement(range(1, M+1), N))
    pt = 0
    for l in L:
        tmp = 0
        for ai, bi, ci, di in zip(a, b, c, d):
            if l[bi-1] - l[ai-1] == ci:
                tmp += di
        pt = max(pt, tmp)
    print(pt)
    # dct = {}
    # for ai, bi, ci, di in zip(a, b, c, d):
    #     if (ai, bi) in dct:
    #         dct[(ai, bi)].add((ci, di))
    #     else:
    #         dct[(ai, bi)] = set()
    #         dct[(ai, bi)].add((ci, di))
    # A = [1 for _ in range(N)]
    # Ab = [False for _ in range(N)]
    # Ab[0] = True
    # mx = 0

    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:
import itertools
a=list(map(int,input().split()))
b=[]
ans=0
c=range(1,a[1]+1)
d=[]
for _ in range(a[2]):
    b.append(list(map(int,input().split())))


for i in itertools.combinations_with_replacement(c,a[0]):
    for l in range(a[2]):
        if i[b[l][1]-1]-i[b[l][0]-1]==b[l][2]:
            ans+=b[l][3]
    d.append(ans)
    ans=0
print(max(d))

Submission status: Accepted

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

from itertools import combinations_with_replacement
A=[0]*N
conditions = []

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

c = combinations_with_replacement(range(1,M+1),N)

total =0
for seq in c:
    total_tmp=0
    for q in conditions:
        if seq[q[1]-1] - seq[q[0]-1] == q[2]:
            total_tmp += q[3]

    total = max(total,total_tmp )

print(total)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
d=list(itertools.combinations_with_replacement(list(range(1,m+1)), n))
ans=0
count=0
for i in range(len(d)):
  for j in range(q):
    if abcd[j][2]==d[i][abcd[j][1]-1]-d[i][abcd[j][0]-1]:
      count+=abcd[j][3]
  if ans<count:
    ans=count
  count=0
print(ans)

Submission status: Accepted

Solution code:
def solve(depth, start, stop):
    global ans
    if depth == N:
        ans = max(ans, sum(d for a, b, c, d in queries if A[b - 1] - A[a - 1] == c))
    else:
        for n in range(start, stop):
            A[depth] = n
            solve(depth + 1, n, stop)

N, M, Q = map(int, input().split())
queries = tuple(tuple(map(int, input().split())) for _ in range(Q))
A = [0] * N
ans = 0
solve(0, 1, M + 1)
print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
abcd=[]
x=[1]
for i in range(q):
    abcd.append(list(map(int,input().split())))
ans=0
def dfs(s):
    global ans
    if(len(s)==n):
        t=0
        for a,b,c,d in abcd:
            if(s[b-1]-s[a-1]==c):
                t+=d
        ans=max(t,ans)
        return 
    p=s[-1]
    while p<=m:
        s.append(p)
        dfs(s)
        p=s.pop()+1
dfs(x)
print(ans)

Submission status: Accepted

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

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

a = []
b = []
c = []
d = []
for i in range(q):
    a_, b_, c_, d_ = list(map(int, input().split()))
    a.append(a_)
    b.append(b_)
    c.append(c_)
    d.append(d_)

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
abcd = []
x = [1]
ans = 0
for _ in range(q):
    abcd.append(list(map(int, input().split())))
    
def dfs(s):
    global ans
    if len(s) == n+1:
        now = 0
        for a, b, c, d in abcd:
            if s[b] - s[a] == c:
                now += d
        ans = max(ans, now)
        return
    p = s[-1]
    while p <= m:
        s.append(p)
        dfs(s)
        p = s.pop() + 1

dfs(x)
print(ans)

Submission status: Accepted

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

ans = 0
for i1 in range(1, m+1):
    for i2 in range(i1, m+1):
        for i3 in range(i2, m+1):
            for i4 in range(i3, m+1):
                for i5 in range(i4, m+1):
                    for i6 in range(i5, m+1):
                        for i7 in range(i6, m+1):
                            for i8 in range(i7, m+1):
                                for i9 in range(i8, m+1):
                                    for i10 in range(i9, m+1):
                                        tmp = 0
                                        A = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        for a, b, c, d in arr: 
                                            if A[b-1] - A[a-1] == c:
                                                tmp += d
                                        ans = tmp if tmp > ans else ans

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)]
 
import itertools
 
A = list(itertools.combinations_with_replacement(range(1,M+1),N))
answer = 0
 
for i in range(len(A)):
    ans = 0
    for j in range(Q):
        if A[i][ abcd[j][1]-1 ] - A[i][ abcd[j][0]-1 ] == abcd[j][2]:
            ans += abcd[j][3]  
    answer = max(answer,ans)
    
print(answer)

Submission status: Accepted

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

import itertools

A = list(itertools.combinations_with_replacement(range(1,M+1),N))
answer = 0

for i in range(len(A)):
    ans = 0
    for j in range(Q):
        if A[i][ abcd[j][1]-1 ] - A[i][ abcd[j][0]-1 ] == abcd[j][2]:
            ans += abcd[j][3]  
    answer = max(answer,ans)
    
print(answer)

Submission status: Accepted

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

ans = 0
def dfs(x,y,combi):
    global ans
    for i in range(x,M+1):
        if y + 1 == N:
            c = 0
            T = combi[:]
            T.append(i)
            for line in A:
                if T[line[1]-1] - T[line[0]-1] == line[2]:
                    c += line[3]
            ans = max(c,ans)
        else:
            K = combi[:]
            K.append(i)
            dfs(i,len(K),K)

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

Submission status: Accepted

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

MOD = 1000000007

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

x = []

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

res = 0
a = [0]*10
for a[0] in range(0, M):
    for a[1] in range(a[0], M):
        for a[2] in range(a[1], M):
            for a[3] in range(a[2], M):
                for a[4] in range(a[3], M):
                    for a[5] in range(a[4], M):
                        for a[6] in range(a[5], M):
                            for a[7] in range(a[6], M):
                                for a[8] in range(a[7], M):
                                    for a[9] in range(a[8], M):
                                        tmp = 0
                                        for i in range(len(x)):
                                            if (a[x[i][1]]- a[x[i][0]]) != x[i][2]:
                                                continue
                                            else:
                                                tmp += x[i][3]
#                                                print(tmp)
                                        res = max(res,tmp)

print(res)

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

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

tmp = []


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


func(n, [])
# print(tmp)


def func2(l):
    global abcd
    global q
    tmptmp = 0
    for i in range(q):
        # print(abcd[i])
        # print(q)
        # print(i)
        if l[abcd[i][1]-1]-l[abcd[i][0]-1] == abcd[i][2]:
            tmptmp += abcd[i][3]
    return tmptmp


tmp2 = []
for i in range(len(tmp)):
    tmp2.append(func2(tmp[i]))
# print(tmp2)
maxx = -100
for i in range(len(tmp2)):
    maxx = max(maxx, tmp2[i])

print(maxx)

Submission status: Accepted

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


def list_A(i=0, a=1):
    if i == n - 1:
        return [[i] for i in range(a, m + 1)]
    lA = []
    for b in range(a, m + 1):
        for A in list_A(i + 1, b):
            lA.append([b] + A)
    return lA


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


answer = max(score(A) for A in list_A())
print(answer)

Submission status: Accepted

Solution code:
import itertools

N, M, Q = (int(x) for x in input().split())
h = [[int(i) for i in input().split()] for _ in range(Q)]
ans = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    temp = 0
    for a, b, c, d in h:
        if A[b-1] - A[a-1] == c:
            temp += d
    ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
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

ans = 0
for S in combinations_with_replacement(range(1, m + 1), n):
     pt = 0
     for i in range(q):
          if S[B[i]] - S[A[i]] == C[i]:
               pt += D[i]
          else:
               pass
     if ans < pt:
          ans = pt
     else:
          pass
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

elements = [i for i in range(1, m + 1)]
A = list(itertools.combinations_with_replacement(elements, n))

point_max = 0
for a in A:
    point = 0
    for c in conds:
        if a[c[1] - 1] - a[c[0] - 1] == c[2]:
            point += c[3]
    point_max = max(point_max, point)

print(point_max)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cw
N,M,Q = map(int, input().split())
cand = cw([i+1 for i in range(M)],N)
fs = [list(map(int, input().split())) for i in range(Q)]

def calc(fs,As):
  count = 0
  for a,b,c,d in fs:
    if As[b-1] - As[a-1] == c:
      count += d
  return count
ans = 0
for As in cand:
  ans = max(ans,calc(fs,As))

print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
A=[list(map(int,input().split())) for i in range(Q)]
ans=0
def make(N,ans):
  def saiki(i,j,_,ans):
    if i==N-1:
      for k in range(j,M+1):
        _[i]=k
        _ans=0
        for a in A:
          if _[a[1]-1]-_[a[0]-1]==a[2]:
            _ans+=a[3]
        ans=max(ans,_ans)
        #print(_)
      return ans
    for k in range(j,M+1):
      _[i]=k
      ans=saiki(i+1,k,_,ans)
    return ans

  _=[1]*N
  i=0
  for j in range(1,M+1):
    ans=saiki(i,j,_,ans)
  return ans
ans=make(N,-1)
print(ans)

Submission status: Accepted

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

for v in itertools.combinations_with_replacement(range(1,m+1),n):
    cnt=0
    for i in range(q):
        if v[li[i][1]-1]-v[li[i][0]-1]==li[i][2]:
            cnt+=li[i][3]
    ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
answer = 0


def main():
    n, m, q = map(int, input().split())
    a = []
    b = []
    c = []
    d = []
    for i in range(q):
        aa, bb, cc, dd = map(int, input().split())
        a.append(aa)
        b.append(bb)
        c.append(cc)
        d.append(dd)

    global answer

    def dfs(seq):
        if len(seq) == n + 1:
            global answer
            now = 0
            for i in range(q):
                if seq[b[i]] - seq[a[i]] == c[i]:
                    now += d[i]
            answer = max(answer, now)
            return
        else:
            for i in range(seq[-1], m + 1):
                dfs(seq + [i])

    dfs([1])
    global answer
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def make(n, A, M):
    if n == 0:
        A_list.append(A)
        return
    for i in range(A[-1], M+1):
        make(n-1, A+[i], M)

n, M, q = map(int, input().split())
A_list = []
for i in range(1, M+1):
    make(n, [i], M)
# print(A_list)

abcd = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for i in A_list:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b] - i[a] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement


def main():
    n, m, q = map(int, input().split())
    a = []
    b = []
    c = []
    d = []
    answer = 0
    for i in range(q):
        aa, bb, cc, dd = map(int, input().split())
        a.append(aa - 1)
        b.append(bb - 1)
        c.append(cc)
        d.append(dd)
    numbers = [i for i in range(1, m + 1)]
    for seq in combinations_with_replacement(numbers, n):
        now = 0
        for i in range(q):
            if seq[b[i]] - seq[a[i]] == c[i]:
                now += d[i]
        answer = max(answer, now)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

  ai,bi,ci,di=map(int,input().split())
  iar.append([ai,bi,ci,di])
kumi=[]
for i in range(1,M+1):
 kumi.append(i)
import itertools
alls=list(itertools.combinations_with_replacement(kumi, N))
maxi=None
maxnum=0
for i in alls:
  goukei=0
  for j in iar:

    abi=i[j[1]-1]
    aai=i[j[0]-1]
    if abi-aai==j[2]:
      goukei=goukei+j[3]
  if goukei>maxnum:
    maxnum=goukei
    maxi=i
#print(maxi)
print(maxnum)

Submission status: Accepted

Solution code:
def dfs(x,cnt):
    global ans
    if cnt != n:
        for i in range(x[-1],m+1):
            dfs(x+[i],cnt+1)
    else:
        cnt = 0
        for a,b,c,d in lis:
            if x[a-1] + c == x[b-1]:
                cnt += d
        ans = max(ans,cnt)
n,m,q = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(q)]
ans = 0
dfs([1],0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q=map(int,input().split())
v=[[] for _ in range(Q)]
o=0
for i in range(Q):
    v[i]=list(map(int,input().split()))
l=list(itertools.combinations(range(M-1+N), N))
for x in l:
    s=0
    a=[]
    for i in range(N):
        a.append(x[i]-i+1)
    for i in range(Q):
        if a[v[i][1]-1]-a[v[i][0]-1]-v[i][2]==0:
            s+=v[i][3]
    if s>o:
        o=s
print(o)

Submission status: Accepted

Solution code:
#many requirement
n,m,q=map(int,input().split())
que=[]
for _ in range(q):
    a,b,c,d=map(int,input().split())
    que.append((a,b,c,d))
from itertools import combinations_with_replacement as cwr
ans=0
raw=[i+1 for i in range(m)]
data=list(cwr(raw,n))
for some in data:
    base=0
    for q in que:
        a,b,c,d=q
        if some[b-1]-some[a-1]==c:
            base+=d
    ans=max(ans,base)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
def main():
    #入力
    readline=stdin.readline
    N,M,Q=map(int,readline().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,readline().split())

    arrays=list(itertools.combinations_with_replacement(range(1,M+1),N))
    max_res=0
    for A in arrays:
        res=0
        for i in range(Q):
            if A[b[i]-1]-A[a[i]-1]==c[i]:
                res+=d[i]
        max_res=max(max_res,res)
    print(max_res)
if __name__=="__main__":
    main()

Submission status: Accepted

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

ans =0

from itertools import combinations_with_replacement

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m, q = map(int, input().split())
  lx = [tuple(map(int, input().split())) for _ in range(q)]
  
  def calc_score(nums):
    return sum([d for a, b, c, d in lx if nums[b-1] - nums[a-1] == c])  
  
  def dfs(nums, depth=0):
    if depth == n:
      return calc_score(nums)
    
    start = 0 if len(nums) == 0 else nums[-1]
    max_score = -1
    for e in range(start, m):
      max_score = max(max_score, dfs(nums + [e], depth+1))
    return max_score
  
  print(dfs([], 0))
    

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res

sys.setrecursionlimit(1923780)

ans=0
def cul(a):
	score=0
	for i in range(q):
		if a[arr[i][1]-1]-a[arr[i][0]-1]==arr[i][2]:
			score+=arr[i][3]
	return score

def dfs(a):
	while 1:
		#print(a)
		# cul
		global ans
		ans = max(ans,cul(a))
		# rec
		if a[0]==m:
			break
		a[n-1]+=1
		for i in range(n-1,0,-1):
			if a[i]>m:
				a[i-1]+=1
				a[i]=0
		for i in range(1,n):
			a[i]=max(a[i],max(a[:i]))


n,m,q = readInts()
arr = []
for _i in range(q):
	arr.append(readInts())
dfs([1]*n)
print(ans)

Submission status: Accepted

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

ans =0

from itertools import combinations_with_replacement

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

print(ans)

Submission status: Accepted

Solution code:
import copy

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

B = []

# 一列の玉を，仕切り板によって分ける問題だと考えれば良い
# 全ての並び方の候補を全探索する。
# 再帰を用いる。

# 深さ優先探索で再帰を当たり前に使えるようにならないといけない。

# 各ボールがどこに入っているかの候補リストを出す再帰関数
# 例えば最初の例題の答えの物は，全ての結果の中から[1, 3, 4]というものを選んだことになる。
def dfs(A, l):
    if l == n:
        # 長さが，Nになったときにのみ，Bというグローバル変数に代入する。
        B.append(A)
    else:
        # ボールを，入る箇所でラベルしながら加えていく。forで回す。
        # ただし，入る箇所は前のものと同じかそれより後ろにならないといけなのでrangeに注意
        for i in range(A[-1], m+1):
            nA = copy.copy(A)
            nA.append(i)
            dfs(nA, l+1)
dfs([1],1)


# ここまでで，ありうる全ての候補が上がった。
ans = 0
for ls in B:
    point = 0
    for que in Q:

        if ls[que[1]-1] - ls[que[0]-1] == que[2]:
            point += que[3]
    ans = max(point, ans)

print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
A = list()
[A.append(list(map(int, input().split()))) for _ in range(Q)]
def generate_sequences(current_sequence, recent_value):
    if len(current_sequence) == N:
        viable.append(current_sequence)
        return
    for i in range(recent_value, M+1):
        generate_sequences(current_sequence+[i], i)
viable = list()
generate_sequences([], 1)
def calc_score(in_list):
  return sum(vec[3] for vec in A if in_list[vec[1]-1]-in_list[vec[0]-1] == vec[2])
print(max(calc_score(in_list) for in_list in viable))

Submission status: Accepted

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

A = [1]*N
def recur(A=A, index=0, lim=M):
    if index>len(A)-2:
        return
    while A[index] <= lim-1:
        A[index] += 1
        yield A[::-1]
        yield from recur(A[:], index+1, A[index])
    return

def get_point(A):
    return sum((A[b[1]-1]-A[b[0]-1]==b[2])*b[3] for b in B)

print(max(0, get_point(A), *(get_point(i) for i in recur())))

Submission status: Accepted

Solution code:
# 重複順列　19C10
from itertools import combinations_with_replacement as cw

n,m,q = map(int, input().split())
a_candidates = cw([i+1 for i in range(m)],n)
fs = [list(map(int, input().split())) for i in range(q)]

def calc(fs,As):
    cnt = 0
    for a,b,c,d in fs:
        a -= 1
        b -= 1
        if As[b]-As[a] == c: cnt += d
    return cnt

ans = 0
for As in list(a_candidates):
    ans = max(ans, calc(fs,As))

print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)


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

ans = 0
p = [0] * n
def dfs(id):
    global ans
    if id < n:
        for i in range(p[id-1], m + 1):
            p[id] = i
            dfs(id + 1)
    else:
        tmp = 0
        for i in range(q):
            if p[b[i]] - p[a[i]] == c[i]:
                tmp += d[i]
        ans = max(ans, tmp)

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

Submission status: Accepted

Solution code:
import itertools
N, M, Q = map(int, input().split())
##とりあえず与えられるリストを受け取る処理
L = []
for i in range(Q):
    L.append(list(map(int, input().split())))
#条件をみたす数列Aとしてありうるものをすべて列挙しておく
ALL = list(itertools.combinations_with_replacement(range(1,M+1), N))
'''
項数N、１以上M以下の数をもつ数列を全部列挙する
全部のパターンについてスコアを求め、その最大値を表示する
'''
result = 0
for suretu in ALL:
    score = 0
    #print("suretu is: ", suretu)
    for i in L:
        #print("i is: ",i)
        #添字がややこしいので注意する
        #最初の組み合わせはsuretu is:  (1, 1, 1)  
        #i is:  [1, 3, 3, 100]　であり、
        #条件はA3-A1=3であれば、100点が得点、である。
        if suretu[i[1]-1]-suretu[i[0]-1]==i[2]:
             score += i[3]
    #print("score is: ",score)
    if score > result:
        result = score
print(result)