Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
from collections import deque

def dfs(n,m):
    d = deque([])
    if n == 1:
        for i in range(1,m+1):
            d.append([i])
        return d
    else:
        dd=dfs(n-1,m)
        for i in range(len(dd)):
            ll=dd.popleft()
            mx=max(ll)
            for j in range(mx,m+1):
                l=ll[:]
                l.append(j)
                d.append(l)
        return d



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

dq=dfs(n,m)
ans=0
ok=True
for i in range(len(dq)):
    aa=dq.popleft()
    scr=0
    for a,b,c,d in x:
        if aa[b-1]-aa[a-1]==c:
            scr+=d
    ans=max(ans,scr)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(n,m):
    d = deque([])
    if n == 1:
        for i in range(1,m+1):
            d.append([i])
        return d
    else:
        dd=dfs(n-1,m)
        for i in range(len(dd)):
            ll=dd.popleft()
            mx=max(ll)
            for j in range(mx,m+1):
                l=ll[:]
                l.append(j)
                d.append(l)
        return d



n,m,q = map(int,input().split())
x=[[0,0,0,0] for _ in range(q)]
cnt=[0 for _ in range(n)]
for i in range(q):
    x[i][0],x[i][1],x[i][2],x[i][3]= map(int,input().split())

dq=dfs(n,m)
ans=0
ok=True
for i in range(len(dq)):
    aa=dq.popleft()
    scr=0
    for a,b,c,d in x:
        if aa[b-1]-aa[a-1]==c:
            scr+=d
    ans=max(ans,scr)

print(ans)

Submission status: Accepted

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

alis=np.array(list(itertools.combinations_with_replacement(range(1,m+1),n)))
#print(alis,len(alis))
ans=np.zeros(len(alis))
#print(ans)
m = map(int, read().split())
for a,b,c,d in zip(m,m,m,m):#got 4
    cond = alis[:, b - 1] - alis[:, a - 1] == c  # 各要素の(b,a)-1番目list(np限定)
    #print(cond)
    ans+=d*cond#Trueのみ加算
print(int(ans.max()))

Submission status: Accepted

Solution code:
import itertools

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

comb_list = list(itertools.combinations_with_replacement(range(1, m + 1), n))
# print(comb_list)
ans = 0
for i in range(len(comb_list)):
    cnt = 0
    for j in range(q):
        if comb_list[i][a[j][1] - 1] - comb_list[i][a[j][0] - 1] == a[j][2]:
            cnt += a[j][3]
    ans = max(ans, cnt)
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())
ans = 0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
  value = 0
  for i in range(Q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      value += d[i]
  ans = max(ans,value)
print(ans)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
a,b,c,d = [],[],[],[]
ans = 0
A = [1]

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)

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

    for i in range(A[-1], m+1):
        A.append(i)
        dfs(A)
        A.pop() #最後の要素を削除
dfs(A)
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 i in range(last,M):
        A.append(i)
        res=max(res,dfs(A))
        A.pop()
    return res
print(dfs([]))

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

a = [1]
ans = 0
def dfs(a):
    global ans
    if len(a) == n+1:
        now = 0
        for i in range(q):
            if a[B[i]] - a[A[i]] == C[i]:
                now += D[i]
        ans = max(ans, now)
        return

    a.append(a[-1])
    while a[-1] <= m:
        dfs(a)
        a[-1] += 1
    a.pop(-1)

dfs(a)
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
 
A = []
B = []
C = []
D = []
 
for i in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
 
 
def dfs(nums):
 
    if len(nums) == N + 1:
        score = 0
        for j in range(Q):
            if nums[B[j]] - nums[A[j]] == C[j]:
                score += D[j]
        return score
 
    max_score = 0
    for i in range(nums[-1], M+1):
        new_nums = nums + [i]
        max_score = max(max_score, dfs(new_nums))
 
    return max_score
 
nums = [1]
res = dfs(nums)
print(res)

Submission status: Accepted

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

k = []
for _ in range(q):
    k.append(list(map(int, input().split(" "))))

max_score = 0
import itertools
for a in itertools.combinations_with_replacement(range(1, m+1), n):
    score = 0
    for i in range(q):
        if a[k[i][1]-1] - a[k[i][0]-1] == k[i][2]:
            score += k[i][3]
    if score > max_score:
        max_score = score
print(max_score)

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

lst = [i for i in range(M)]

ans = 0

for tmp in combinations_with_replacement(lst, N):
  score = 0
  for a, b, c, d, in ABCD:
    if tmp[b-1] -tmp[a-1] == c:
      score += d
    ans = max(ans, score)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools as it

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

ar = [[0]*4]*q

for i in range(q):
    ar[i] = [int(s) for s in input().split()]

A = list(it.combinations_with_replacement(list(range(1,m+1)),n))
mx = 0

for cnd in A:
    mx_tmp=0
    for i in range(q):
        if(cnd[ar[i][1]-1] - cnd[ar[i][0]-1] == ar[i][2]):
            mx_tmp += ar[i][3]
    mx = max(mx,mx_tmp)

print(mx)

Submission status: Accepted

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

from itertools import combinations_with_replacement

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

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

lst = [i for i in range(M)]

ans = 0
for tmp in combinations_with_replacement(lst, N):
    score = 0
    for a, b, c, d in ABCD:
        if tmp[b - 1] - tmp[a - 1] == c:
            score += d
    ans = max(ans, score)

print (ans)

Submission status: Accepted

Solution code:
#n,m,q = 3,4,3 # n個で m以下の A
#arr = [[1, 3, 3, 100], [1, 2, 2, 10], [2, 3, 2, 10]]

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

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

score = 0
for a1 in range(1,m+1):
  for a2 in range(a1,m+1):
    for a3 in range(a2,m+1):
      for a4 in range(a3,m+1):
        for a5 in range(a4,m+1):
          for a6 in range(a5,m+1):
            for a7 in range(a6,m+1):
              for a8 in range(a7,m+1):
                for a9 in range(a8,m+1):
                  for a10 in range(a9,m+1):
                    x = [0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10]
                    tmp_score=0
                    for a,b,c,d in arr:
                      if(x[b]-x[a] == c):
                        tmp_score += d
                    score = max(score,tmp_score)
print(score)

Submission status: Accepted

Solution code:
import itertools as it
n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

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

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

max_list = [0] * len(A)
index = 0
for item in A:
    for i in range(q):
        if item[b[i]-1] - item[a[i]-1] == c[i]:
            max_list[index] += d[i]
    index += 1

# print(max_list)
print(max(max_list))

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 = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
 
n = len(A)
score = np.zeros(n, np.int32)
# m = map(int, read().split())

for i in range(Q):
	a, b, c, d = map(int, readline().split())
	cond = A[:, b - 1] - A[:, a - 1] == c
	score += d * cond
 
print(score.max())

Submission status: Accepted

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

abcd = []

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

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

P = []


def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])


dfs(1, [])

ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
## coding: UTF-8


N, M, Q = map(int,input().split())
'''
lq = []
for i in range(Q):
    lq.append(list(map(int,input().split())))
'''
lq = [list(map(int, input().split())) for _ in range(Q)]
#print(lq)

dfs = []
for i in range(1, M+1):
    dfs.append([i])
#print(dfs)

def add(l):
    ret = []
    for i in range(len(l)):
        last = l[i][-1]
        for j in range(last, M+1):
            ret.append(l[i] + [j])
    return ret

for i in range(N-1):
    dfs = add(dfs)
#print(dfs)


m = -1
for i in range(len(dfs)):
    A = dfs[i]
    tmp = 0
    for j in range(len(lq)):
        aj = lq[j][0]
        bj = lq[j][1]
        cj = lq[j][2]
        dj = lq[j][3]
        #print('i:{}, j:{}, A:{}, [aj, bj, cj, dj]:{}'.format(i, j, A, lq[j]))
        #print('A[bj-1]:{}, A[aj-1]:{}, A[bj-1]-A[aj-1]:{}, cj:{}, ==?:{}, dj:{}'.format(A[bj-1], A[aj-1], A[bj-1]-A[aj-1], cj,   A[bj-1]-A[aj-1]==cj  , dj))
        #print('i:{}, j:{}, A:{}, lq[j]:{}'.format(i, j, A, lq[j]))
        #print('A[lq[j][i]-1]:{}, A[lq[j][0] - 1]:{}'.format(A[lq[j][i]-1], A[lq[j][0] - 1]))
        #if(A[lq[j][i]-1] - A[lq[j][0] - 1] == lq[2]):
            #tmp += lq[3]
        if(A[bj-1]-A[aj-1] == cj):
            tmp += dj
    #print('i:{}, A:{}, tmp:{}'.format(i, A, tmp))
    if(tmp > m):
        m = tmp    
print(m)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from itertools import combinations_with_replacement as combi
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, m, q = MII()
    query = [MII() for _ in range(q)]
    # l = [i for i in range(1,m+1)]
    # maxv = 0
    # for v in combi(l,n):
    #     sumv = 0
    #     for a,b,c,d in query:
    #         if v[b-1]-v[a-1] == c:
    #             sumv += d
    #     maxv = max(maxv, sumv)
    # print(maxv)
    def score(A):
        res = 0
        for a, b, c, d in query:
            if A[b-1]-A[a-1] == c:
                res += d
        return res

    def dfs(A):
        if len(A) == n:
            return score(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([]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M,Q=map(int, input().split())
    ABCD=[tuple(map(int, input().split())) for _ in range(Q)]

    def f(l):
        res=0
        for a,b,c,d in ABCD:
            if l[b]-l[a]==c: res+=d
        return res

    ans=0
    l=[]
    stk=[(1,1)]
    while stk:
        o,v=stk.pop()
        if o==1:
            stk.append((0,1))
            l.append(v)
            if len(l)==N+1:
                ans = max(ans, f(l))
            else:
                for i in range(l[-1],M+1):
                    stk.append((1,i))
        else:
            l.pop()
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#写経：再起で書き直し
#https://drken1215.hatenablog.com/entry/2020/05/04/190252

def dfs(A):
    # 終端条件 --- 10 重ループまで回したら処理して打ち切り
    ans = 0
    if len(A) == N:
        return score(A)
    prev_last = A[-1] if len(A) > 0 else 1
    for v in range(prev_last, M+1):
        A.append(v)
        ans = max(ans, dfs(A))
        A.pop()  # これが結構ポイント
    return ans

def score(A):
    temp = 0
    for q in abcd:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            temp += q[3]
    return temp


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

Submission status: Accepted

Solution code:
def comb(n,r):
    r=min(r,n-r)
    c=1
    for i in range(r):
        c=c*(n-i)/(r-i)
    return int(c)

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

npat=comb(N+M,M)
A=[1 for _ in range(N)]
ans=0

for i in range(npat):
    temp=0
    for j in range(Q):
        if A[a[j][1]-1]-A[a[j][0]-1]==a[j][2]:
            temp+=a[j][3]
    ans=max(ans,temp)
#    print(A)
#    print(temp)
    A[-1]+=1
    if A[-1]>M and i<npat-1:
        k=1
        while max(A)>M and k<N:
            A[N-k-1]+=1
            A[N-k]=A[N-k-1]
            k+=1
            for l in range(1,k):
                A[N-l]=A[N-k]
    if min(A)>M:
        break
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = [int(n) for n in input().split()]
a, b, c, d = [list(x) for x in zip(*[[int(n) for n in input().split()] for _ in range(Q)])]
ans = 0

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

    for v in range(A[-1], M+1):
        A.append(v)
        dfs(A)
        A.pop()

dfs([1])
print(ans)

Submission status: Accepted

Solution code:
N, M, Q = [int(n) for n in input().split()]
a, b, c, d = [list(x) for x in zip(*[[int(n) for n in input().split()] for _ in range(Q)])]
ans = 0
def dfs(A):
    global ans
    if len(A) == N+1:
        now = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(ans, now)
        return
    tail = A[-1] if len(A) > 0 else 1
    for v in range(tail, M+1):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])
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,b,c,d=map(int,input().split())
    A[i]=a-1
    B[i]=b-1
    C[i]=c
    D[i]=d
smax=0
def dfs(L):
    global smax
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(L) == N:
        s=0
        for i in range(Q):
            if L[B[i]] - L[A[i]] == C[i]:
                s+=D[i]
        if s>smax:
            smax=s
        return

    #数列の最後の値からMまでの範囲を回す。もし最後の値が空なら1になる
    prev_last = L[-1] if len(L) > 0 else 1
    for v in range(prev_last,M+1):
        L.append(v)
        dfs(L)
        L.pop()

dfs([])#L=[]のリストとなっている
print(smax)

Submission status: Accepted

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

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

Max = 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):
                    A = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    Sum = 0
                    for s in S:
                      if A[s[1]]-A[s[0]]==s[2]:
                        Sum += s[3]
                    Max = max(Max, Sum)                          

print(Max)

Submission status: Accepted

Solution code:
#165 
#C

from itertools import *

n,m,q = map(int, input().split())
# n,m,q = 3,4,3
# ln_condi = [[1, 3, 3, 100], [1, 2, 2, 10], [2, 3, 2, 10]]
ln_condi  = []
for i in range(q):
    ln_condi.append(list(map(int, input().split())))
#print(ln_condi)
p = list(range(1,m+1))
a = list(combinations_with_replacement(p,n))
#print(a)
summax  = 0
for i in a:
    sumd = 0
    for j in range(q):
        if i[ln_condi[j][1]-1] - i[ln_condi[j][0]-1] == ln_condi[j][2]:
            sumd +=  ln_condi[j][3]
    if sumd > summax:
        summax = sumd
print(summax)

Submission status: Accepted

Solution code:
s = list(map(int,input().split()))
n=s[0]
m=s[1]
q=s[2]
f=[]
ans=0

for i in range(q):
    s = list(map(int, input().split()))
    f.append([s[0],s[1],s[2],s[3]])

def score_cal(y):
    score=0
    for i in f:
        if y[i[1]-1]-y[i[0]-1]==i[2]:
            score+=i[3]
    return score

def dfs(A):
    if len(A)==n:
        score=score_cal(A)
        global ans
        if ans<score:
            ans=score
        return 
    for v in range(A[-1],m+1):
        A.append(v)
        dfs(x)
        A.pop()

for i in range(1,m+1):
    x=[]
    x.append(i)
    dfs(x)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

kouho = [i for i in range(1, M+1)]

_max = 0
for j, comb in enumerate(itertools.combinations_with_replacement(kouho, N)):
    _sum = 0
    for __list in _list:
        if comb[__list[1]-1] - comb[__list[0]-1] == __list[2]:
            _sum += __list[3]
        # print(comb)
        # print(__list)
        #print(_sum)
    # print('-----------')
    if _sum > _max:
        _max = _sum

print(_max)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
S=[0]*Q;t=0;d=0;A=[0]*10
for i in range(Q):
  a,b,c,d=map(int,input().split())
  S[i]=[a,b,c,d]
#print(S)
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):
                    d=0
                    A=[i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for i in range(Q):
                      if A[S[i][1]-1]-A[S[i][0]-1]==S[i][2]:
                        d=d+S[i][3]
                    t=max(t,d)
                    
print(t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
N, M, Q = [int(n) for n in input().split()]
X = [[int(n) for n in input().split()] for _ in range(Q)]
ans = 0
for A in combinations_with_replacement(range(1, M+1), N):
    t = 0
    for x in X:
        if A[x[1]-1]-A[x[0]-1] == x[2]: t += x[3]
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,q = map(int,input().split())
t=[]
def dfs(l):
  if len(l) == n:
    return [l]

  if len(l) == 0:
    t=1
  else:
    t=l[-1]
  res=[]
  for i in range(t, m+1):
    temp=l+[i]
    for j in dfs(temp):
      res.append(j)
  return res

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

ans=0
l=dfs([])
for i in l:
  temp=0
  for a,b,c,d in t:
    if i[b-1]-i[a-1] == c:
      temp+=d
  ans=max(ans,temp)
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
A=[]
for i in range(q):
  a[i],b[i],c[i],d[i]=map(int,input().split())
def score(A):
  sum=0
  for (ai,bi,ci,di) in zip(a,b,c,d):
    if A[bi-1]-A[ai-1]==ci:
      sum+=di
  return sum
def fbs(A):
  if len(A)==n:
    return score(A)
  if len(A)>0:
    pre_last=A[-1]
  else:
    pre_last=0
  res=0
  for v in range(pre_last,m):
    A.append(v)
    res=max(res,fbs(A))
    A.pop()
  return res

print(fbs(A))

Submission status: Accepted

Solution code:
import itertools
import heapq
N,M,Q = list(map(int,input().split()))
list1 = [list(map(int,input().split())) for i in range(Q)] 
q1 = []
heapq.heapify(q1)

ans = [None]
def dfs(x,n2,m1):
  if len(x) == n2:
    heapq.heappush(q1,-sum(x1[3] for x1 in list1 if x[x1[1]-1]-x[x1[0]-1] == x1[2]))
  else:
    for i in range(1,m1+1,1):
      if i >= x[-1]:
        x.append(i)
        dfs(x,n2,m1)
        x.pop()

dfs([1],N,M)
print(-heapq.heappop(q1))

Submission status: Accepted

Solution code:
import itertools as it
n,m,q=map(int,input().split())
kouho=list(it.combinations_with_replacement(range(1,m+1),n))


lis=[]
for i in range(q):
  lis.append(list(map(int,input().split())))  
keep=0
for i in range(0,len(kouho)):
  attack=kouho[i]
  point=0
  for j in range(0,q):
    if attack[lis[j][1]-1]-attack[lis[j][0]-1]==lis[j][2]:
      point+=lis[j][3]
  if point>keep:
    keep=point
print(keep)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = list(map(int,input().split()))
list1 = [list(map(int,input().split())) for i in range(Q)] 
  
ans = [0]
def dfs(x,n2,m1):
  if len(x) == n2:
    score = sum(x1[3] for x1 in list1 if x[x1[1]-1]-x[x1[0]-1] == x1[2])
    if score > ans[0]:
      ans[0] = score
  else:
    for i in range(1,m1+1,1):
      if i >= x[-1]:
        x.append(i)
        dfs(x,n2,m1)
        x.pop()

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

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

#Aの定義
A=list(itertools.combinations_with_replacement(range(1,M+1), N))

#Aを総当たりで、得点計算
best_score=0
for k in range(len(A)):
    score=0
    for i in range(Q):
        if A[k][b[i]]-A[k][a[i]]==c[i]:
            score+=d[i]
    best_score=max(best_score,score)

print(best_score)

Submission status: Accepted

Solution code:
import copy

n, m, q = map(int, input().split())
a = [list(map(int, input().split())) for i in range(q)]
s = []
def dfs(A):
    if len(A) == n:
        s.append(copy.deepcopy(A))
        return
    prev_last = A[-1] if len(A) > 0 else 1
    for i in range(prev_last, m+1):
        A.append(i)
        dfs(A)
        A.pop()

dfs([])

ans = 0
for i in s:
    S = 0
    for j in range(q):
        if i[a[j][1]-1] - i[a[j][0]-1] == a[j][2]:
            S += a[j][3]
    ans = max(ans, S)
#print(a)
#print(s)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M,Q = map(int,input().split())
ABCD = [[int(i) for i in input().split()] for j in range(Q)]
ans = []
#数列を全部作る(組み合わせの全列挙)→各数列に対して得点を計算する
As = itertools.combinations_with_replacement(range(1,M+1),N)

for A in As:
    score = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1] == c:
            score += d
    ans.append(score)
print(max(ans))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
li = [1]
ans = 0
a_li = []
b_li = []
c_li = []
d_li = []

for i in range(q):
    a, b, c, d = map(int, input().split())
    a_li.append(a)
    b_li.append(b)
    c_li.append(c)
    d_li.append(d)


def dfs(li):
    score = 0

    for i in range(li[-1], m+1):
        if len(li) == n+1:
            for j in range(q):
                if li[b_li[j]] - li[a_li[j]] == c_li[j]:
                    score += d_li[j]
                    global ans

                    if score > ans:
                        ans = score
            return 0

        li.append(i)
        dfs(li)
        li.pop()


dfs(li)
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())
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:
#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, M, Q = [int(_) for _ in input().split()]
abcd = [[int(_) for _ in input().split()] for i in range(Q)]

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

ma = 0
scores = []
for i in com:
    score = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            score += j[3]
    if score > ma:
        ma = score
print(ma)

Submission status: Accepted

Solution code:
def dfs(a, ans):
    if len(a) < n + 1:
        cur = a[-1]
        while (cur <= m):
            a.append(cur)
            ans = dfs(a, ans)
            a.pop()
            cur += 1
    else:
        score = 0
        for c in condition:
            if (a[c[1]] - a[c[0]] == c[2]):
                score += c[3]
        ans = max(ans, score)
        return ans
    return ans


n, m, q = [int(val) for val in input().split()]
condition = []
ans = 0
for i in range(q):
    condition.append([int(val) for val in input().split()])
ans = dfs([1], ans)

print(ans)