Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
import itertools

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

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

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

max_score = 0

for i in a:
    temp = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            temp += j[3]
        
    max_score = max(max_score, temp)

print(max_score)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

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

ans = 0
def dfs(before):
    global ans
    if len(before) == N:
        score = 0
        for a,b,c,d in ABCD:
            a -= 1
            b -= 1
            if before[b] - before[a] == c:
                score += d
        ans = max(ans,score)
        return
    for i in range(before[-1],M + 1):
        before.append(i)
        dfs(before)
        before.pop()

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
## C Many Requirements
import itertools
N, M, Q = map(int, input().split() )
X = [list( map( int,input().split() ) ) for x in range(Q)]

listd = []
A = list( itertools.combinations_with_replacement( [i for i in range(1, M+1) ], N ) )
for a in A:
    sumd = 0
    for q in range(Q):
        if a[X[q][1]-1] - a[X[q][0]-1] == X[q][2]:
            sumd += X[q][3]
    listd.append(sumd)
print( max(listd) )

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(Q)]
A = [1] * N
ans = 0

for a, b, c, d in l:
    if A[b-1] - A[a-1] == c:
        ans += d

if M > 1:
    while True:
        A[-1] += 1
        if A[-1] == M + 1:
            for i in range(1, N):
                A[-(i+1)] += 1
                for k in range(N-(i+1), N):
                    A[k] = A[-(i+1)]
                if A[-(i+1)] != M + 1:
                    break
            
        ans_ = 0
        for a, b, c, d in l:
            if A[b-1] - A[a-1] == c:
                ans_ += d
        ans = max(ans, ans_)

        if A[0] == M:
            break
print(ans)

Submission status: Accepted

Solution code:
# 全探索で行う
N, M, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
A = [1]

def dfs(now):
    if len(now) == N:
        global ans
        tmp_ans = 0
        for a, b, c, d in query:
            a -= 1
            b -= 1
            if now[b] - now[a] == c:
                tmp_ans += d
        ans = max(ans, tmp_ans)
    else:
        for i in range(now[-1], M+1):
            tmp = now.copy()
            tmp.append(i)
            dfs(tmp)


ans = 0
dfs(A)
print(ans)

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

Submission status: Accepted

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

ans=-1
#全探索
seq = tuple(range(M))

com=list(itertools.combinations_with_replacement(seq, N))

for li in com:
    re=0
    for i in range(Q):
        a=S[i][0]-1
        b=S[i][1]-1
        c=S[i][2]
        d=S[i][3]
        if li[b]-li[a] == c:
            re += d
    if re > ans:
        ans=re

print(ans)

Submission status: Accepted

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

ABCD=[[0]]*Q
i=0
while i<Q:
    ABCD[i]=list(map(int,input().split()))
    i+=1

import itertools
seq=list(range(1,M+1))
AN=list(itertools.combinations_with_replacement(seq,N))

ans=0
for Aj in AN:
    count=0
    for A,B,C,D in ABCD:
        if Aj[B-1]-Aj[A-1]==C:
            count+=D
    ans=max(ans,count)

print(ans)

Submission status: Accepted

Solution code:
n,m,q = list(map(int,input().split()));
 
data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));
 
A = [1]*n;
ans = 0;
As = [A];
 
for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;
 
 
print(ans);

Submission status: Accepted

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

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


def calcPoint(num):
    ret = 0
    for q in range(Q):
        if num[query[q][1] - 1] - num[query[q][0] - 1] == query[q][2]:
            ret += query[q][3]

    return ret


ans = 0


def dfs(suu, keta):
    global ans
    if keta == N:
        ans = max(ans, calcPoint(suu))
        # print(*suu)
        return

    co = suu.copy()

    for i in range(suu[keta - 1], M):
        co[keta] = i
        dfs(co, keta + 1)


retsu = [0] * N

dfs(retsu, 1)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for c in list(itertools.combinations_with_replacement(range(1, m+1), n)):
    total = 0
    for i in range(q):
        if c[li[i][1]-1] - c[li[i][0]-1] == li[i][2]:
            total += li[i][3]
    if total > ans:
        ans = total
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=deque()  #0,0,0,0,0....,0
def make(a,b,c): #a=list b=maxlen c=max
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+[i],b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Submission status: Accepted

Solution code:
def point(A, Q):
    return sum(q[3] for q in Q if A[q[1]] - A[q[0]] == q[2])

def solve(A, n, Q, M):
    if n == len(A):
        return point(A, Q)

    ans = 0
    for i in range(A[n-1], M+1):
        A[n] = i
        ans = max(ans, solve(A, n+1, Q, M))
    
    return ans

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

    print(solve(A, 1, kumi, M))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, Q = lr()
ABCD = [lr() for _ in range(Q)]
answer = 0

def dfs(A):
    global answer
    if len(A) == 11:
        temp = 0
        for a, b, c, d in ABCD:
            if A[b] - A[a] == c:
                temp += d
        if temp > answer:
            answer = temp
        return  
    back = A[-1]
    while back <= M:
        dfs(A + [back])
        back += 1

dfs([1])
print(answer)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10**7)
#X=int(input())
N,M,Q=map(int,input().split())
S=[[]for i in range(Q)]
for i in range(Q):
    a=list(map(int,input().split()))
    S[i]=a
ans=0
T=0
def solve(l):
    global ans
    if len(l)>=N:
        tmp=0
        for k in range(Q):
            if l[S[k][1]-1]-l[S[k][0]-1]==S[k][2]:
                tmp+=S[k][3]
        ans=max(ans,tmp)
        return
    for i in range(l[-1],M+1):
        solve(l+[i])
solve([1])
print(ans)

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)]
s=0
for p in combinations_with_replacement(range(1,m+1),n):
    t=0
    for a,b,c,d in abcd:
        t+=d*(p[b-1]-p[a-1]==c)
    s=max(s,t)
print(s)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
for A in combinations_with_replacement(range(1, M+1), N):
  tmp = 0
  for a, b, c, d in query:
    if A[b-1] - A[a-1] == c:
      tmp += d
  ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=deque()  #0,0,0,0,0....,0
def make(a,b,c): #a=list b=maxlen c=max
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+deque([i]),b,c)
for t in range(1,m+1):
    make(deque([t]),n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy

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

queue = deque()
for i in range(1, M+1):
    queue.append([i])
while queue[0] != [1] * N:
    x = queue.popleft()
    for i in range(x[-1], M+1):
        y = copy(x)
        y.append(i)
        queue.append(y)

score_max = 0
for A in queue:
    score = 0
    for a, b, c, d in X:
        if A[b-1] - A[a-1] == c:
            score += d
    score_max = max(score, score_max)

print(score_max)

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

max_point = 0
for i in itertools.combinations_with_replacement(range(1, M+1), N):
    # print(i)
    point = 0
    for abcd in ABCD:
        if i[abcd[1]-1] - i[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    max_point = max(max_point, point)
print(max_point)

Submission status: Accepted

Solution code:
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  #0,0,0,0,0....,0
def make(a,b,c): #a=list b=maxlen c=max
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+[i],b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Submission status: Accepted

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

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

l = []
def dfs(lis, y):
  if len(lis) == N:
    l.append(lis)
    return
  else:
    for i in range(y, M+1):
      z = list(lis)
      z.append(i)
      dfs(z, i)
    return
      
dfs([], 1)

ans = 0
for A in l:
  tmp = 0
  for a, b, c, d in query:
    if A[b-1] - A[a-1] == c:
      tmp += d
  ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
'''ika tako
制約条件を見て、戦略を決める（制約が戦略を決める）
配列の添え字を、なるべくシンプルにする（KISS）
広義単調増加（同じ数もOK）なので、重複順列（仕切り板で分ける）
求める数列の候補である　重複順列を列挙し、重複順列毎にscoreを求め、
そのscoreの最大値が答（数列を求めるのではなく、数列を点検する）
入力は空のリストにappendで追加
入力の際、0-indexとなるように、引く1をする（後で考えるのはメンドウ）
重複順列毎に回し、更に、クエリ毎に条件式で得点を求める、二重ループ
scoreは、答の候補である重複順列毎の得点
求めるansは、そのscoreの最大値
この二つを区別すること
'''

from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    queries.append((a, b, c, d))

ans = 0
for arr in combinations_with_replacement(range(m), n):
    score = 0
    for a, b, c, d in queries:
        if arr[b] - arr[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,q = map(int,input().split())
query = [[int(i) for i in input().split()] for _ in range(q)]

def f(A):
    if len(A) == n+1:
        # print(A)
        cnt = 0
        for i in range(q):
            a,b,c,d = query[i]
            if A[b]-A[a] == c: cnt += d
        return cnt
    res = 0
    for i in range(A[-1],m+1):
        res = max(res,f(A+[i]))
    return res

print(f([1]))

Submission status: Accepted

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

ans = 0
a = [0 for i in range(n)]
def dfs(p):
    global ans
    if p == 0:
        for i in range(1, m+1):
            a[p] = i
            dfs(p+1)
    else:
        for i in range(a[p-1], m+1):
            a[p] = i
            if p != n-1:
                dfs(p+1)
            else:
                temp = 0
                for j in range(q):
                    ai, bi, ci, di = kumi[j]
                    ai, bi = ai-1, bi-1
                    if a[bi] - a[ai] == ci:
                        temp += di
                ans = max(ans, temp)

dfs(0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
p = []
ans = 0
for _ in range(q):
    p.append(list(map(int, input().split())))
for A in combinations_with_replacement(range(1,m+1), n):
    cnt = 0
    for i in range(q):
        if A[p[i][1]-1] - A[p[i][0]-1] == p[i][2]:
            cnt += p[i][3]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

x = list(combinations_with_replacement(range(1,m+1),n))
y = []
for _ in range(q):
  a,b,c,d = map(int, input().split())
  y.append([a,b,c,d])
  
ans = 0
for i in x:
  k = 0
  for j in y:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      k += j[3]
  ans = max(ans,k)
print(ans)

Submission status: Accepted

Solution code:
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  #0,0,0,0,0....,0
def make(a,b,c): #a=list b=maxlen c=max
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            k=copy.copy(a)
            k.append(i)
            make(k,b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Submission status: Accepted

Solution code:
import itertools

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

for _ in range(Q):
    ai, bi, ci, di = map(int, input().split())
    ABCD.append((ai, bi, ci, di))

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

for a in A:
    tmp = 0
    for abcd in ABCD:
        if a[abcd[1]-1] - a[abcd[0]-1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())
li = []
for _ in range(q):
    li.append(list(map(int,input().split())))
kumi = list(itertools.combinations_with_replacement(range(1,m+1), n))
score = 0
for k in kumi:
    each_score = 0
    for l in li:
        a = l[0]
        b = l[1]
        diff = l[2]
        katen = l[3]
        if k[b-1]-k[a-1] == diff:
            each_score += katen
    if each_score > score:
        score = each_score
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())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        dfs(j,M,N,tmp)
    
q=dfs(1,M,N,[])


f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Submission status: Accepted

Solution code:
import itertools
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    A_ = itertools.combinations_with_replacement(range(1, M + 1), N)
    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        abcd.append((a, b, c, d))

    ans = 0
    for A in A_:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                tmp += d

        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  #0,0,0,0,0....,0
def make(a,b,c): #a=list b=maxlen c=max
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            k=copy.copy(a)
            k.append(i)
            make(k,b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)


    
#

Submission status: Accepted

Solution code:
def dfs(arr, min_nx):
    ans = 0
    if len(arr) == n:
        tmp = 0
        for a,b,c,d in lst:
            if arr[b-1] - arr[a-1] == c:
                tmp += d
        return tmp
    else:
        for nx in range(min_nx, m+1):
            new_arr = arr + [nx]
            score = dfs(new_arr, nx)
            ans = max(ans, score)
    return ans
n,m,q = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([], 1)
print(ans)

Submission status: Accepted

Solution code:
def main():
  n, m, q = map(int, input().split() )
  a = [0] * q
  b = [0] * q
  c = [0] * q
  d = [0] * q
  for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split() )
  A = [1] * (n + 1)
  A[0] = 0
  ans = 0
  while A[0]==0:
    tmp = 0
    for i in range(q):
      if( A[b[i]]-A[a[i]]==c[i] ):
        tmp += d[i]
    ans = max(ans, tmp)
    A[n] += 1
    for i in range(1,n+1):
      if( A[i]>m ):
        i-=1
        A[i] += 1
        t = A[i]
        for j in range(i,n+1):
          A[j] = t
        break
  print(ans)

main()

Submission status: Accepted

Solution code:
import itertools

n,m,q = map(int, input().split())
A = list(itertools.combinations_with_replacement(range(1, m+1), n))
qs = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for t in A:
  temp = 0
  for a,b,c,d in qs:
    if t[b-1] - t[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())
abcd = [tuple(map(int, input().split())) for i in range(Q)]
ans = 0
for x in combinations_with_replacement(range(1, M+1), 10):
    tmp = 0

    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if x[a] + c == x[b]:
            tmp += d
    ans = max(ans, tmp)


print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    L = [list(map(int, input().split())) for _ in range(Q)]
    # L = sorted(L, key=lambda x: x[-1])
    answer = 0
    As = list(combinations_with_replacement([i for i in range(1, M + 1)], N))
    for A in As:
        cnt = 0
        for l in L:
            a = l[0] - 1
            b = l[1] - 1
            c = l[2]
            d = l[3]
            if A[b] - A[a] == c:
                cnt += d
        if answer < cnt:
            answer = cnt
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score_ret = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score_ret += d
        return score_ret
    
    else:
        for nu in range(min_lim, m+1):
            new_nums = nums + [nu]
            score = dfs(new_nums, length+1, nu)
            ans = max(ans, score)
    return ans

n,m,q = map(int,input().split())
req = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([-1], 0, 1)
print(ans)

Submission status: Accepted

Solution code:
#提出用
n,m,q = list(map(int, input().split()))

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

for i in range(q):
    aa,bb,cc,dd = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

ans = 0

def dfs(la):
    global ans
    if len(la)==n+1:
        sum_d=0
        #print(la)
        #print(ans)
        for i in range(q):
            if la[b[i]] - la[a[i]] == c[i]:
                sum_d += d[i]
        if sum_d > ans:
            ans = sum_d
        return
    
    la.append(la[-1])
    while(la[-1]<=m):
        dfs(la.copy())
        la[-1] += 1
        

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
def main(k, s):
    if k == n:
        return sum(d * (s[b] - s[a] == c) for a, b, c, d in abcd)
    return max(main(k + 1, s + [ai]) for ai in range(s[-1], m + 1))

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    print(main(0, [1]))

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
L = []
for i in range(Q):
  L.append(list(map(int, input().split())))
  L[i][0]-=1
  L[i][1]-=1

import itertools

l =list(range(1,M+1))
ans=0

v=list(itertools.combinations_with_replacement(l,N))

for arr in v:
  score=0
  for a,b,c,d in L:
    if (arr[b] - arr[a])==c:
      
      score+=d
  ans=max(ans,score)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans=0

for l in itertools.combinations_with_replacement(range(1,m+1),n):
    val=0
    for i in range(q):
        if l[qry[i][1]-1]-l[qry[i][0]-1]==qry[i][2]:
            val+=qry[i][3]
    ans=max(ans,val)
    
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):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[i for i in range(M)]
for i in itertools.combinations_with_replacement(A,N):
  s=0
  for k in range(Q):
    if i[b[k]-1]-i[a[k]-1]==c[k]:
      s+=d[k]
  maxs=max(maxs,s)
      
print(maxs)

Submission status: Accepted

Solution code:
def dfs(seq):
    global ans
    if len(seq) == n:
        tmp = 0
        for i in range(q):
            if seq[b[i]] - seq[a[i]] == c[i]:
                tmp += d[i]
        ans = max(tmp, ans)
        return 
       
    if seq == []:
        start=0
    else:
        start = seq[-1]

    for i in range(start,m):
        dfs(seq+[i])

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
dfs([])
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as combi

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

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

score = 0
for iter in combi([i for i in range(1, m+1)], n):
    score = max(points(sorted(iter), queries), score)

print(score)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from itertools import combinations_with_replacement, combinations
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, q = LI()
L = LIR(q)
ans = 0
for arr in combinations_with_replacement(range(1, m + 1), n):
    ret = 0
    for a, b, c, d in L:
        if arr[b - 1] - arr[a - 1] == c:
            ret += d
    ans = max(ans, ret)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0
for x in itertools.combinations_with_replacement(range(1, M+1), N):
    #print(x)
    count = 0
    for i in range(Q):
        if x[b[i]] - x[a[i]] == c[i]:
            count += d[i]
    ans = max(ans,count)

print(ans)

Submission status: Accepted

Solution code:
def dfs(A):
  global ans
  if len(A)==N: 
    now=0
    for i in l:
      if A[i[1]-1]-A[i[0]-1]==i[2]:
        now+=i[3]
    ans=max(ans,now)
    return A

  A.append(A[-1])
  while A[-1]<=M:
    dfs(A[:])
    A[-1]+=1
    
  
N,M,Q=[int(x) for x in input().rstrip().split()]
A=[1]
l=[]
ans=0
for i in range(Q):
  abcd=[int(x) for x in input().rstrip().split()]
  l.append(abcd)
dfs(A)
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m, q = map(int, input().split())
    l = []
    for i in range(q):
        l1, l2, l3, l4 = map(int, input().split())
        l.append([l1, l2, l3, l4])
    B = []
    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):
                                            L = [a, b, c, d, e, f, g, h, i, j]
                                            A = []
                                            for I in range(n):
                                                A.append(L[I])
                                            C = 0
                                            for k in range(q):
                                                if A[l[k][1] - 1] - A[l[k][0] - 1] == l[k][2]:
                                                    C += l[k][3]
                                            B.append(C)
    print(max(B))
    
main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,q = map(int, input().split())
array = np.array(list(itertools.combinations_with_replacement(range(1,m+1),n)))
result = np.zeros((len(array)), dtype="int")
for i in range(q):
    temp = 0
    a,b,c,d = map(int, input().split())
    where = array[:,b-1] - array[:,a-1] == c
    result[where] += d
print(max(result))

Submission status: Accepted

Solution code:
import itertools
import numpy as np

def main():
    ans = 0
    n,m,q = map(int, input().split())
    qs = [list(map(int, input().split())) for _ in range(q)]
    l = list(itertools.combinations_with_replacement(range(1, m+1), n))
    for t in l:
        temp = 0
        for a,b,c,d in qs:
            if t[b-1] - t[a-1] == c:
                temp += d
        ans = max(ans, temp)
                
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
l = []
for i in range(q):
    l1, l2, l3, l4 = map(int, input().split())
    l.append([l1, l2, l3, l4])
B = []
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):
                                        L = [a, b, c, d, e, f, g, h, i, j]
                                        A = []
                                        for I in range(n):
                                            A.append(L[I])
                                        C = 0
                                        for k in range(q):
                                            if A[l[k][1] - 1] - A[l[k][0] - 1] == l[k][2]:
                                                C += l[k][3]
                                        B.append(C)
print(max(B))