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())
a = itertools.combinations_with_replacement([i for i in range(1,M+1)], N)
abcdQ = [list(map(int, input().split())) for i in range(Q)]
maxSumD = 0
for A in a:
  sumD = 0
  for abcd in abcdQ:
    if A[abcd[1]-1]-A[abcd[0]-1] == abcd[2]:
      sumD += abcd[3]
  maxSumD = max(maxSumD, sumD)
  
print(maxSumD)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import defaultdict

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()

def main():
	n, m, q = (int(x) for x in rll())
	pts = defaultdict(lambda: 0)
	for _ in range(q):
		a, b, c, d = (int(x) for x in rll())
		pts[(a, b, c)] = d

	seq = []
	ans = float('-inf')

	def calcval(s):
		score = 0
		curr = defaultdict(lambda: 0)
		for (a, b, c), d in pts.items():
			if s[b-1] - s[a-1] == c and d > curr[(a, b)]:
				score -= curr[(a,b)]
				curr[(a,b)] = d
				score += d
		return score

	def dfs(i, maxlen, maxdig, prev = None):
		nonlocal ans
		if i == maxlen:
			score = calcval(seq)
			ans = max(ans, score)
			return
		start = 1 if prev is None else prev
		for num in range(start, maxdig + 1):
			seq.append(num)
			dfs(i+1, maxlen, maxdig, num)
			seq.pop()

	dfs(0, n, m)
	stdout.write(str(ans));stdout.write("\n")
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
abcd=[]
for i in range(Q):
    abcdabcd=list(map(int,input().split()))
    abcd.append(abcdabcd)
#入れるAはリスト、[]で表現
def cal(A):
    t=0
    for abcdi in abcd:
        a=abcdi[0]
        b=abcdi[1]
        c=abcdi[2]
        d=abcdi[3]
        if A[b-1]-A[a-1]==c:
            t+=d
    return t

maxi=0
for i in range(1,M+1):
    if N==1:
        maxi=max(maxi,cal([i]))
    for j in range(i,M+1):
        if N==2:
            maxi=max(maxi,cal([i,j]))
        for k in range(j,M+1):
            if N==3:
                maxi=max(maxi,cal([i,j,k]))
            for l in range(k,M+1):
                if N==4:
                    maxi=max(maxi,cal([i,j,k,l]))
                for m in range(l,M+1):
                    if N==5:
                        maxi=max(maxi,cal([i,j,k,l,m]))
                    for n in range(m,M+1):
                        if N==6:
                             maxi=max(maxi,cal([i,j,k,l,m,n]))
                        for o in range(n,M+1):
                            if N==7:
                                maxi=max(maxi,cal([i,j,k,l,m,n,o]))
                            for p in range(o,M+1):
                                if N==8:
                                    maxi=max(maxi,cal([i,j,k,l,m,n,o,p]))
                                for q in range(p,M+1):
                                    if N==9:
                                        maxi=max(maxi,cal([ij,k,l,m,n,o,p,q]))
                                    for r in range(q,M+1):
                                        if N==10:
                                            maxi=max(maxi,cal([i,j,k,l,m,n,o,p,q,r]))
                                        

print(maxi)

Submission status: Accepted

Solution code:
#標準入力
N, M, Q = map(int, input().split())
abcd = []
for _ in range(Q):
    tmp = list(map(int, input().split()))
    abcd.append(tmp)

#実装
import itertools as it
A_candidate = list(it.combinations_with_replacement(range(1, M + 1), N))
ans = 0
for i in range(len(A_candidate)):
    tmp = 0
    for j in range(Q):
        ABCD = abcd[j]
        if A_candidate[i][ABCD[1] - 1] - A_candidate[i][ABCD[0] - 1] == ABCD[2] :
            tmp += ABCD[3]
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
#標準入力
N, M, Q = map(int, input().split())
abcd = []
for _ in range(Q):
    tmp = list(map(int, input().split()))
    abcd.append(tmp)

#実装
import itertools as it
A_candidate = list(it.combinations_with_replacement(range(1, M + 1), N))
ans = 0
for i in range(len(A_candidate)):
    tmp = 0
    for j in range(Q):
        if A_candidate[i][abcd[j][1] - 1] - A_candidate[i][abcd[j][0] - 1] == abcd[j][2] :
            tmp += abcd[j][3]
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import itertools


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

    A, B, C, D = [], [], [], []
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(c)
        D.append(d)
    if m == 1:
        return sum(D)
    ans = 0
    length = m+n-1
    for item in itertools.combinations(range(length), m-1):
        ptn = []
        num = 1
        p = 0
        for i in range(length):
            if i == item[p]:
                num += 1
                p += 1
                p = min(m-2, p)
                continue
            ptn.append(num)
        tmp = 0
        for k in range(q):
            if (ptn[B[k]-1] - ptn[A[k]-1]) == C[k]:
                tmp += D[k]

        ans = max(tmp, ans)
    return ans

print(main())

Submission status: Accepted

Solution code:
# ここから入力
from itertools import combinations_with_replacement
from itertools import accumulate
n, m, q = map(int, input().split())
a = []
for i in range(q):
    a.append(list(map(int, input().split())))
# ここまで入力
# 重複組合せ
x = 0
for i in combinations_with_replacement(range(1, m + 1), n):
    ans = []
    for j in a:
        if i[j[1] - 1] - i[j[0] - 1] == j[2]:
            ans.append(j[3])
    if x < sum(ans):
        x = sum(ans)
print(x)

Submission status: Accepted

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

al=[]
bl=[]
cl=[]
dl=[]
l=[]
ansl=[0 for i in range(n+1)]
for i in range(q):
    a,b,c,d=map(int,input().split())
    al.append(a)
    bl.append(b)
    cl.append(c)
    dl.append(d)
    l.append([a,b,c,d])

def score(seq):
    temp=0
    for a,b,c,d in zip(al,bl,cl,dl):
        if seq[b-1]-seq[a-1]==c:
            temp+=d
    return temp

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

Submission status: Accepted

Solution code:
# Problem C - Many Requirements

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

# dfs search
def dfs(nums, score, ini_num, keta):
    if keta==N+1:
        tmp_score = 0
        for q in query:
            if nums[q[1]]-nums[q[0]]==q[2]:
                tmp_score += q[3]
        score = max(score, tmp_score)
    else:
        for i in range(ini_num, M+1):
            nums[keta] = ini_num
            score = max(score, dfs(nums, score, i, keta+1))
    return score

# initialization
nums = [0]*(N+1)
max_score = 0

max_score = dfs(nums, 0, 1, 1)
# output
print(max_score)

Submission status: Accepted

Solution code:
n,m,q= map(int, input().split())
s = [list(map(int, input().split()))for i in range(q)]
a =[1]*(n+1)
z =[]
def dfs(n,m,a,now):
    if now==n:
        b=a.copy()
        z.append(b)
        return
    for i in range(a[now],m+1):
        a[now]=i
        a[now+1]=i
        dfs(n,m,a,now+1)
dfs(n,m,a,0)
ma = 0
for i in range(len(z)):
    ans=0
    for j in range(q):
        if z[i][s[j][1]-1]-z[i][s[j][0]-1]==s[j][2]:
            ans+=s[j][3]
    ma=max(ma,ans)
print(ma)

Submission status: Accepted

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

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

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

ans = 0
for i in range(len(c)):
    check = 0
    for j in range(q):
        if c[i][a[j][1]-1] - c[i][a[j][0]-1] == a[j][2]:
            check = check + a[j][3]
    ans = max(ans,check)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
N,M,Q=list(map(int, (stdin.readline().strip().split())))
q=[]
num_list=[]
number=[]
score=[0]
daburi=[]
for i in range(1,M+1):number.append(i)
for _ in range(Q):
    a,b,c,d=list(map(int, (stdin.readline().strip().split())))
    q.append([a,b,c,d])
def dfs(num_list,i):
    if i==M and len(num_list)<N:
        return
    if len(num_list)!=N:
        a=num_list.copy()
        num_list.append(number[i])
        dfs(num_list,i)
        dfs(a,i+1)
    else:
        ans=0
        for a,b,c,d in q:
            if num_list[b-1]-num_list[a-1]==c:
                ans+=d
        score[0]=max(ans,score[0])



dfs(num_list,0)
print(score[0])

Submission status: Accepted

Solution code:
from sys import stdin
import itertools
N,M,Q=list(map(int, (stdin.readline().strip().split())))
q=[]
num_list=[]
number=[]
score=[0]
for i in range(1,M+1):number.append(i)
for _ in range(Q):
    a,b,c,d=list(map(int, (stdin.readline().strip().split())))
    q.append([a,b,c,d])
def dfs(num_list,i):
    if i==M and len(num_list)<N:
        return
    if len(num_list)!=N:
        a=num_list.copy()
        num_list.append(number[i])
        dfs(num_list,i)
        dfs(num_list,i+1)
        dfs(a,i+1)
    else:
        ans=0
        for a,b,c,d in q:
            if num_list[b-1]-num_list[a-1]==c:
                ans+=d
        score[0]=max(ans,score[0])



dfs(num_list,0)
print(score[0])

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                               
    # for i in range(q):
    #     if A[b[i]]-A[a[i]] == c[i]:
    #         tmp += d[i]
    # return tmp

def dfs(A):
    if len(A) == n:
        return score(A)   
    res = 0
    if len(A) > 0:                # prev_last = A[-1] if len(A) > 0 else 0
        prev_last = A[-1] 
    else:
        prev_last = 0
    for i in range(prev_last, m):
        A.append(i)
        res = max(res, dfs(A))    # 再起を呼び出しながら、最大値の更新
        A.pop()
    return res

print(dfs([]))

Submission status: Accepted

Solution code:
import itertools
n,m,q = map(int,input().split())  
stock = list(range(1,m+1))
A = list(itertools.combinations_with_replacement(stock,n))
lst = []
for i in range(q):
    a = list(map(int,input().split()))
    lst.append(a)
lstx = []    
for k in range(len(A)):
    sum = 0    
    for j in range(q):
        if A[k][lst[j][1]-1] - A[k][lst[j][0]-1] == lst[j][2]:
            sum += lst[j][3]
    lstx.append(sum)    
print(max(lstx))

Submission status: Accepted

Solution code:
n,m,q = map(int, input().split())
Q = [[]]*q
for i in range(q):
  Q[i] = list(map(int, input().split()))
 
#10H10 = 92378
mx = 0

import copy
import sys
sys.setrecursionlimit(10**6)

def count_d(A):
  global mx
  if len(A)<n:
    for i in range(A[-1],m+1):
      A_next = copy.deepcopy(A)
      A_next.append(i)
      count_d(A_next)
      
  if len(A)==n:
    res = 0
    for i in range(q):
      a, b, c, d = Q[i]
      if A[b-1] - A[a-1] == c:
        res += d
    if res>mx:
      mx = res
      
for i in range(1, m+1):
  count_d([i])
  
print(mx)

Submission status: Accepted

Solution code:
from collections import deque
import itertools

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

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

print(ans)

Submission status: Accepted

Solution code:
import itertools
# ありうる数列全探索する
def main():
    # input
    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(要素数N,1<=Ai<=M)について全パターンを出す
    arrA = itertools.combinations_with_replacement([i for i in range(1,M+1)], N)
    # 全探索
    max1 = 0
    for arr in arrA:
        tmp = 0
        for i in range(Q):
            if arr[b[i]-1]-arr[a[i]-1] == c[i]:
                tmp+=d[i]
        max1 = max(tmp,max1)

    print(max1)

main()

Submission status: Accepted

Solution code:
length, max_num, num_range = list(map(int, input().split()))
import itertools

ds = [0]
get_point = 0

a_list = []
b_list = []
c_list = []
d_list = []

for n in range(num_range):
    a, b, c, d = (list(map(int, input().split())))
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

    # ds.append(ds[n] + d)

# print(ds)
ans=0
for _, A in enumerate(itertools.combinations_with_replacement(range(1, max_num + 1), length)):
    tmp = 0
    for i,d in enumerate(d_list):
        a= A[a_list[i] - 1]
        b = A[b_list[i] - 1]

        if b-a == c_list[i]:
            # print(A, a, b,ds[i+1], c_list[i])
            tmp+=d
            ans=max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q=map(int,input().split())
x=[list(map(int,input().split())) for y in range(q)]
ans=0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
  new_ans=0
  for i in range(q):
    if A[x[i][1]-1]-A[x[i][0]-1]==x[i][2]:
      new_ans +=x[i][3]
  ans=max(ans,new_ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

nums = [int(e) for e in input().split()]

list0 = []
for i in range(0,nums[2]):
    list1 = [int(e) for e in input().split()]
    list0.append(list1)

A = []
A0 = list(range(1,nums[1]+1))
for x in itertools.combinations_with_replacement(A0,nums[0]):
    A1 = list(x)
    A1.sort()
    A.append(A1)

d = []
for i in range(0,len(A)):
    d0 = 0
    for j in range(0,nums[2]):
        if A[i][list0[j][1]-1] - A[i][list0[j][0]-1] == list0[j][2]:
            d0 = d0 + list0[j][3]
    d.append(d0)

print(max(d))

Submission status: Accepted

Solution code:
from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**4)
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
import math  
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x 
def Divisors(n) : 
    l = []  
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                l.append(i) 
            else : 
                l.append(i)
                l.append(n//i)
    return l
prime=[]
def SieveOfEratosthenes(n): 
    global prime
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]: 
            f.append(p)
    return f
q=[]       
def dfs(n,d,v,c):
    global q
    v[n]=1
    if n not in d:
        return v
    x=d[n]
    q.append(n)
    j=c
    for i in x:
        if i not in v:
            v=dfs(i,d,v,c+1)
            # print(f)
    return v
f=[]
import itertools
def printCombination(arr, n, r): 
    data = [0]*r; 
    combinationUtil(arr, data, 0,  
                    n - 1, 0, r); 

def combinationUtil(arr, data, start,  
                    end, index, r):
    global f   
    # print("IN",index,r)
    if (index == r): 
        ff=[]
        for j in range(r):
            ff.append(data[j]) 
        f.append(ff) 
        return; 
 
    i = start;  
    # print(i,end,r)
    while(i <= end and end + 1 >= 0): 
        data[index] = arr[i]; 
        combinationUtil(arr, data, i ,  
                        end, index + 1, r); 
        i += 1; 
"""*******************************************************"""
def main():
    n,m,q=cin()
    a=[]
    b=[]
    for _ in range(q):
        u,v,w,x=cin()
        b.append((u-1,v-1,w,x))
    for i in range(m):
        a.append(i+1)
    an=0
    printCombination(a,m,n)
    # print(f)
    for c in f:
        # print(c)
        ans=0
        for i in b:
            if c[i[1]]-c[i[0]]==i[2]:
                ans+=i[3]
        # print(ans)
        an=max(ans,an)
    print(an)

######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()

Submission status: Accepted

Solution code:
n, m, q = list(map(int, input().split(" ")))
Q = [list(map(int, input().split(" "))) for i in range(q)]
Q = [[i[0] - 1, i[1] - 1, i[2], i[3]] for i in Q]

def calc(arr: list):
    return sum([i[3] for i in Q if arr[i[1]] - arr[i[0]] == i[2]])

def get_array(arr: list, num):
    if len(arr) == n:
        return calc(arr)
    return max([get_array(arr + [i], i) for i in range(num, m + 1)])

print(get_array([], 1))

Submission status: Accepted

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))
n,m,q = I2()
r = []
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
ans = []
import copy
def dfs(A):
    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.append(now)
        return
    A.append(A[-1])
    while (A[-1] <= m):
        dfs(copy.copy(A))
        A[-1] += 1
if __name__ == "__main__":
    for i in range(q):
        a[i],b[i],c[i],d[i] = I2()
    dfs([1])
    print(max(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations_with_replacement as comb
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(comb(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Accepted

Solution code:
#数列Aの取りうるものをcombinations_with_replacementで作って、全探索
#データ入力
from itertools import combinations_with_replacement
N,M,Q = (int(x) for x in input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

#
all_A =[i for i in range(1,M+1)] #数列Aの取りうる値
A =[0]*N
ans =[]
for A in combinations_with_replacement(all_A,N):
    count =0
    for i in range(Q):
        ai,bi,ci,di =abcd[i]
        if A[bi-1] -A[ai-1] ==ci:
            count += di
    ans.append(count)
print(max(ans))

Submission status: Accepted

Solution code:
import itertools

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

counter_l = list((itertools.combinations_with_replacement(range(1, m+1), n)))
for i in range(len(counter_l)):
    counter_l[i] = list(counter_l[i])


for j in counter_l:
    tmp = 0
    for k in range(q):
        if j[l[k][1] - 1] - j[l[k][0] - 1] == l[k][2]:
            tmp += l[k][3]
    cnt = max(cnt, tmp)

print(cnt)

Submission status: Accepted

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

l=[]
for n in range(Q):
    l.append(list(map(int,input().strip().split())))

def score(A):
    SUM=0
    for i in range(Q):
        if A[l[i][1]]-A[l[i][0]]==l[i][2]:
            SUM+=l[i][3]
    return SUM    

ans=0
def dfs(A,N,M):
    if len(A)==N+1:
        global ans
        ans=max(ans,score(A))
        return
    else:
        last=A[-1]
        for n in range(last,M+1):
            A.append(n)
            dfs(A,N,M)
            A.pop()

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

Submission status: Accepted

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


def dfs(x):
    if len(x) == N + 1:
        res = 0
        for a, b, c, d in X:
            if x[b] - x[a] == c:
                res += d
        return res

    res = 0
    last = x[-1]
    for v in range(last, M + 1):
        x.append(v)
        res = max(res, dfs(x))
        x.pop()

    return res

print(dfs([1]))

Submission status: Accepted

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


def dfs(x):
    if len(x) == N + 1:
        res = 0
        for a, b, c, d in X:
            if x[b] - x[a] == c:
                res += d
        return res

    res = 0
    x.append(x[-1])
    while x[-1] <= M:
        res = max(res, dfs(x))
        x[-1] += 1
    x.pop()

    return res

print(dfs([1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    ans = 0
    for A in itertools.combinations_with_replacement(range(1, M+1), N):
        ans = max(sum([d[i]
                       for i in range(Q) if A[b[i]]-A[a[i]] == c[i]]), ans)
    print(ans)


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)) - 1
        b[i] = int(next(tokens)) - 1
        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

n,m,q = map(int, input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
highScore = 0

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

for A in itertools.combinations_with_replacement(range(1,m+1),n):
    score = 0
    for o in range(q):
        if A[b[o]-1] - A[a[o]-1] == c[o]:
            score += d[o]
    highScore = max(score,highScore)

print(highScore)

Submission status: Accepted

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

ans = 0
for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp = 0
    for a, b, c, d in values:
        if comb[b - 1] - comb[a - 1] == c: tmp += d
    ans = max(tmp, ans)
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())

import itertools
import numpy as np    
    
ans = 0  
  
for A in itertools.combinations_with_replacement(range(1,M+1),N):
  score = 0
  for i in range(Q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      score += d[i]
  ans = max(score,ans)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m,q = list(map(int,input().split()))
lis = []
for i in range(q):
    lis.append(list(map(int,input().split())))
l = [x for x in range(1,m+1)]
c_list = list(itertools.combinations_with_replacement(l,n))
ans = 0
for con in c_list:
    tmp = 0
    for item in lis:
        if con[item[1]-1]-con[item[0]-1] == item[2]:
            tmp += item[3]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
import sys

def LI(): return map(int, sys.stdin.readline().rstrip().split())

N, M, Q = LI()

Q_groups = []
for _ in range(Q):
    Q_groups.append([*LI()])

max_score = 0
for p in combinations_with_replacement(range(1, M + 1), r=N):
    temp_score = 0
    for q in Q_groups:
        if p[q[1] - 1] - p[q[0] - 1] == q[2]:
            temp_score += q[3]
    max_score = max(max_score, temp_score)

print(max_score)

Submission status: Accepted

Solution code:
import itertools

N,M,Q=map(int,input().split())
abcd = [tuple(int(v2) for v2 in input().split()) for _ in range(Q)]
#print(abcd)
def getScore(ary):
  score = 0
  for a,b,c,d in abcd:
    #print(a,b,ary)
    if ary[b-1]-ary[a-1] == c:
      score+=d
  return score
C=[i for i in range(M+N-1)]
As =[]
for c in itertools.combinations(C,N):
  #print(c)
  tmp = [0 if i in c else 1 for i,v in enumerate(C) ]
  l = [sum(tmp[:i]) for i,v in enumerate(tmp) if v == 0]
  As.append(l)
#print(As)
scores = [getScore(a) for a in As]
#print(scores)
print(max(scores))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement

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

x = 0
for i in combinations_with_replacement(range(1,m+1), n):
    s = 0
    for j in a:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            s += j[3]
    if x < s:
        x = s
print(x)

Submission status: Accepted

Solution code:
n,m,q = [int(i) for i in input().split()]
p = []
for i in range(q):
  p.append([int(i) for i in input().split()])
dmax = 0
a = [1 for i in range(n)]
while True:
  d = 0
  for i in range(q):
    if a[p[i][1]-1]-a[p[i][0]-1] == p[i][2]:
      d += p[i][3]
  if d > dmax:
    dmax = d
  if a[0] == m:
    break
  c = 1
  l = a.pop()
  while l==m:
    l = a.pop()
    c += 1
  for i in range(c):
    a.append(l+1)
    
print(dmax)