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: Time Limit Exceeded

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

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

abcd.sort()
max_point = 0
for i_bin in range(1 << q):
    A = [0] * (n + 1)
    tmp_max_point = 0
    for index in range(q):
        if i_bin >> index & 1 == 1:
            a, b, c, d = abcd[index]
            if A[a] == 0 and A[b] == 0 and 1 + c <= m:
                for list_index in range(n+1):
                    if A[list_index] == 0:
                        continue
                    if list_index < a and A[list_index] > 1 or list_index > a and A[list_index] < 1:
                        break
                    if list_index > b and  A[list_index] < 1 + c or list_index < b and A[list_index] > 1 + c:
                        break
                else:
                    A[a] = 1
                    A[b] = A[a] + c
                    tmp_max_point += d
                # if A[b-1] <= A[a] + c <= A[min(n,b+1)] or A[min(n, b+1)] == 0:
                #     A[a] = 1
                #     A[b] = A[a] + c
                #     tmp_max_point += d
            elif A[a] != 0 and A[b] == 0 and A[a] + c <= m:
                for list_index in range(n+1):
                    if A[list_index] == 0:
                        continue
                    if list_index < a and A[list_index] > A[a] or list_index > a and A[list_index] < A[a]:
                        break
                    if list_index > b and  A[list_index] < A[a] + c or list_index < b and A[list_index] > A[a] + c:
                        break
                else:
                    A[b] = A[a] + c
                    tmp_max_point += d
                # if A[b-1] <= A[a] + c <= A[min(n, b+1)] or A[min(n, b+1)] == 0:
                #     A[b] = A[a] + c
                #     tmp_max_point += d
            elif A[a] == 0 and A[b] != 0 and A[b] - c >= 1:
                for list_index in range(n+1):
                    if A[list_index] == 0:
                        continue
                    if list_index < a and A[list_index] > A[b] - c or list_index > a and A[list_index] < A[b] - c:
                        break
                    if list_index > b and  A[list_index] < A[a] + c or list_index < b and A[list_index] > A[a] + c:
                        break
                else:
                    A[a] = A[b] - c
                    tmp_max_point += d
                # if A[max(0, a-1)] <= A[b] - c <= A[a+1] or A[min(n, b+1)] == 0:
                #     A[a] = A[b] - c
                #     tmp_max_point += d
            elif A[a] != 0 and A[b] != 0 :
                if A[b] - A[a] == c:
                    tmp_max_point += d
    
    max_point = max(max_point, tmp_max_point)
    # print(tmp_max_point)
    # print(a,b,c,d)
    # print(A)

print(max_point)

# print(abcd)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,m,q=map(int,input().split())
lst=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    lst.append([a-1,b-1,c,d])
ans=0
for i in range(1,2**q):
    const=[]
    for j in range(q):
        if (i>>j)&1:
            const.append(lst[j])
    s=[None]*n
    tmp=0
    for a,b,c,d in const:
        if s[b]==s[a]==None:
            s[a]=0
            s[b]=c
            tmp+=d
        elif s[a]==None:
            s[a]=s[b]-c
            tmp+=d
        elif s[b]==None:
            s[b]=s[a]+c
            tmp+=d
        else:
            if s[b]-s[a]!=c:
                tmp=0
                break
            else:
                tmp+=d
    for j in range(n):
        if s[j]==None:
            s[j]=0
    p=max(s)-min(s)
    switch=0
    for j in range(n-1):
        if s[j]>s[j+1]:
            switch=1
    if switch==0:
        if p<=m-1:
            ans=max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
for A in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1] - A[a-1] == c:
      score += d
  ans = max(ans,score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1] - A[a-1] == c:
      score += d
  if ans < score:
    ans = score
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    if A[abcd[i][1]-1] - A[abcd[i][0]-1] == abcd[i][2]:
      score += abcd[i][3]
  ans = max(ans,score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
A = [1 for i in range(N)]
for A in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[b-1] - A[a-1] == c:
      score += d
  ans = max(ans,score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
ans = 0
for aa in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if aa[b-1] - aa[a-1] == c:
      score += d
  #ans = max(ans,score)
  if ans < score:
    ans = score
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#cited from maspy
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
#A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
#n = len(A)

ans = 0
for aa in np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N))):
  score = 0
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if aa[b-1] - aa[a-1] == c:
      score += d
  ans = max(ans,score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#cited from maspy
import itertools
import numpy as np

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))
n = len(A)
score = [0]*n
ans = 0
for j in range(n):
  for i in range(Q):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if A[j][b-1] - A[j][a-1] == c:
      score[j] += d
  ans = max(ans,score[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,q=map(int,input().split())
a=[]
for i in range(q):
  a.append(list(map(int,input().split())))
ans=0
data=set([''.join(list(i)) for i in list(permutations('1'*(m-1)+'0'*n))])
for i in data:
  s=[1]*(n+1)
  cnt=0
  k=0
  for j in range(n+m-1):
    if i[j]=='1':s[k]+=1
    else:
      s[k+1]=s[k]
      k+=1
  for x,y,z,w in a:
    if s[y-1]-s[x-1]==z:cnt+=w
  ans=max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n,m,q=map(int,input().split())
a=[]
for i in range(q):
  a.append(list(map(int,input().split())))
ans=0
data=set([''.join(list(i)) for i in list(permutations('1'*(m-1)+'0'*n))])
for i in data:
  s=[1]*(n+m)
  cnt=0
  t=[]
  for j in range(n+m-1):
    if i[j]=='1':s[j]+=1
    else:t.append(s[j])
    s[j+1]=s[j]
  for x,y,z,w in a:
    if t[y-1]-t[x-1]==z:cnt+=w
  ans=max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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

#print(query)

import itertools
cnbr = []  #組み合わせ
for i in range(m+1):
    for j in itertools.combinations_with_replacement(range(m), n):
        cnbr.append(j)

#print(cnbr)
points = [0] * len(cnbr)

for _ in range(len(cnbr)):
    for a,b,c,d in query:
        if cnbr[_][b - 1] - cnbr[_][a - 1] == c:
            points[_] += d

print(max(points))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1<<q):
  score = 0
  A = [0]*(n+1)
  for j in range(q):
    if (i>>j)&1 == 1:
      A[abcd[j][1]] = A[abcd[j][0]] + abcd[j][2]
      if A[abcd[j][1]] > m:
        break
  for j in range(q):
    if A[abcd[j][1]] - A[abcd[j][0]] == abcd[j][2]:
      score += abcd[j][3]
  if score > ans:
    ans = score
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
a,b,c,d = [],[],[],[]
for i in range(q):
  ai,bi,ci,di = map(int, input().split())
  a.append(ai)
  b.append(bi)
  c.append(ci)
  d.append(di)

ans = 0
for i in range(1<<q):
  score = 0
  A = [0]*(n+1)
  for j in range(q):
    if (i>>j)&1 == 1:
      A[b[j]] = A[a[j]] + c[j]
  for j in range(q):
    if A[b[j]] - A[a[j]] == c[j]:
      score += d[j]
  if score > ans:
    ans = score
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

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

comb_A = list(itertools.combinations_with_replacement(list_tmp, N))


max_score = 0
for A in comb_A:
    tmp_score = 0
    #print(A)
    for q in range(Q):
        #print(A)
        a = abcd_list[q][0]
        b = abcd_list[q][1]
        c = abcd_list[q][2]
        d = abcd_list[q][3]

        A_a = A[a - 1]
        A_b = A[b - 1]

        if(A_b - A_a == c):
            tmp_score += d
        
    max_score = max(max_score, tmp_score)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
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())
AA = [0] * n + [1] * (m-1)
A = [0] * n
ans=0
for i in permutations(AA):
    j=1
    p=0
    for k in i:
        if k==0:
            A[p]=j
            p+=1
        elif k==1:
            j+=1
        if p==n:
            break
    point =0
    for k in range(q):

        if A[b[k]-1] - A[a[k]-1] == c[k]:
            point += d[k]
    ans = max(ans, point)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n,m,q = map(int, input().split())
list_ = [list(map(int, input().split())) for _ in range(q)]
tmp = list(range(1,m+1))
cases = [sorted(list(arr)) for arr in itertools.product(tmp, repeat=n)]

max_score = 0
visited = set()
for arr in cases:
  score = 0
  if str(arr) in visited:
    pass
  else:
    visited.add(str(arr))
    for arr_2 in list_:
      if arr[arr_2[1]-1] - arr[arr_2[0]-1] == arr_2[2]:
        score+=arr_2[3]
  max_score = max(max_score, score)
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import combinations_with_replacement as combi

N, M, Q = map(int, input().split())
road = deque([input().split() for i in range(Q)])
l = [i+1 for i in range(M)]
point = 0
for v in combi(l, N):
    tmp = 0
    for j in range(Q):
        a, b, c, d = map(int, road[j])
        if v[b-1] - v[a-1] == c:
            tmp += d
    point = max(point, tmp)

print(point)

Submission status: Time Limit Exceeded

Solution code:
#inport
import sys
import numpy as np
import itertools as itlt
from collections import deque

#input 
    
N,M,Q = [int(x) for x in sys.stdin.readline().split()]
g = [0,0,0,0] * Q
#print(g)
for _ in range(Q):
    g[_] = [int(x) for x in sys.stdin.readline().split()]

choice = list(np.arange(1, M+1))
combi = list(itlt.combinations_with_replacement(choice, N))
score = 0

for i in range(np.size(combi,axis = 0)):
    score_tmp = 0
    combi_tmp = combi[i]
    for j in range(Q):
        if (combi_tmp[g[j][1]-1] - combi_tmp[g[j][0]-1]) == g[j][2]:
            score_tmp = score_tmp + g[j][3]
    if score_tmp > score:
        score = score_tmp

print(score)

Submission status: Time Limit Exceeded

Solution code:
#inport
import sys
import numpy as np
import itertools as itlt
from collections import deque

#input 
    
N,M,Q = [int(x) for x in sys.stdin.readline().split()]
g = [0,0,0,0] * Q
#print(g)
for _ in range(Q):
    g[_] = [int(x) for x in sys.stdin.readline().split()]

choice = list(np.arange(1, M+1))
combi = list(itlt.combinations_with_replacement(choice, N))
score = 0

for i in range(np.size(combi,axis = 0)):
    score_tmp = 0
    for j in range(Q):
        if (combi[i][g[j][1]-1] - combi[i][g[j][0]-1]) == g[j][2]:
            score_tmp = score_tmp + g[j][3]
    if score_tmp > score:
        score = score_tmp

print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]

def calc(x): # type(x) == str型
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

q = deque([1])
ans = 0
while q:
    tmp = q.popleft()
    tmp = str(tmp)
    if len(tmp) == N:
        ans = max(ans, calc(tmp))
    else:
        for i in range(int(tmp[-1]), M+1):
            q.append(tmp+str(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x): # type(x) == str型
		ans = 0
		for a, b, c, d in A:
			if int(x[b-1]) - int(x[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = q.popleft()
		tmp = str(tmp)
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)
	
resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

abcd = [input() for _ in range(q)]

x = itertools.combinations_with_replacement(range(1,m+1),n)
tmp = 0
ans = 0
for xi in x:
  tmp = 0

  for i in abcd:
    a,b,c,d = map(int,i.split())
    if xi[b-1] - xi[a-1] == c:
      tmp += d
  ans = max(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# DFS
from collections import deque
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
arr = list(range(1, M+1))
ans = 0
for i in range(1, M+1):
    st = deque([])
    st.append((i, str(i)))
    while st:
        p, l = st.pop()
        if len(l) == N:
            cur = 0
            for y in ls:
                if int(l[y[1]-1]) - int(l[y[0]-1]) == y[2]:
                    cur += y[3]
            ans = max(ans, cur)
        else:
            for j in range(p, M+1):
                st.append((j, l + str(j)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#inport
import sys
import numpy as np
import itertools as itlt
from collections import deque

#input
g = list([])
N,M,Q = [int(x) for x in sys.stdin.readline().split()]
for _ in range(Q):
    g.append([int(x) for x in sys.stdin.readline().split()])

choice = list(np.arange(1, M+1))
combi = list(itlt.combinations_with_replacement(choice, N))
score = 0

for i in range(np.size(combi,axis = 0)):
    score_tmp = 0
    for j in range(Q):
        if (combi[i][g[j][1]-1] - combi[i][g[j][0]-1]) == g[j][2]:
            score_tmp = score_tmp + g[j][3]
    if score_tmp > score:
        score = score_tmp

print(score)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x): # type(x) == str型
		ans = 0
		for a, b, c, d in A:
			if int(x[b-1]) - int(x[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = q.popleft()
		tmp = str(tmp)
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)
	
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x: str) -> int:
		s = str(x)
		ans = 0
		for i in A:
			a, b, c, d = i[0], i[1], i[2], i[3]
			if int(s[b-1]) - int(s[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = str(q.popleft())
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def basen(x,n):
    if (int(x/n)):return basen(int(x/n),n)+str(x%n)
    return str(x%n)
def f(s,n):
    L=['0']*(n-len(s))+list(s)
    return list(map(lambda x:int(x)+1,L))
def main():
    N,M,Q=tuple(map(int,sys.stdin.readline().split()))
    R,res=[],0
    for _ in [0]*Q:
        a,b,c,d=tuple(map(int,sys.stdin.readline().split()))
        R.append((a,b,c,d))
    for i in range(M**N):
        A,y=f(basen(i,M),N),0
        if any(list(map(lambda i:A[i+1]<A[i],range(N-1)))):continue
        for a,b,c,d in R:y=y+d if A[b-1]-A[a-1]==c else y
        if res<y:res=y
    print(res)
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m, q = list(map(int,input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
#print(sets)
mx = 0
nums = list(range(1,m+1))
for h in itertools.combinations_with_replacement(nums,n):
    mxtemp = 0
    for j in range(q):
        a = sets[j][0]
        b = sets[j][1]
        if list(h)[b-1] - list(h)[a-1] == sets[j][2]:
            mxtemp += sets[j][3]
    if mxtemp > mx:
        mx = mxtemp
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q = (int(x) for x in input().split())
l = []
a = [1,2,3,4,5,6,7,8,9,10]
b = []
c = []
d = []


for i in range(q):
    l.append([])
    l[i]=list(map(int, input().split()))
    
for i in itertools.combinations_with_replacement(a[:m], r=n):#考えられる数列
    if i not in b:
        b.append(i) 
        
    
for i in range(len(b)):#それぞれの数列の得点表
    d.append(0)

for i in range(q):
    w=l[i][0]-1#a
    x=l[i][1]-1#b
    y=l[i][2]#c
    z=l[i][3]#d
    for j in range(len(b)):
        if b[j][x]-b[j][w]==y:
            d[j]+=z

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
import numpy as np 
N,M,Q = (int(x) for x in input().split())
abcd =np.zeros((Q,4),dtype=int)
for i in range(Q):
    abcd[i] = list(map(int, input().split()))
abcd[:,0] -=1 #添え字にするから、-1
abcd[:,1] -=1 #添え字にするから、-1

#リストAを要素数N,最大値Mで全列挙
ans =[]
#for i in range(1,N+1):
for a in combinations_with_replacement (range(1,M+1),N):
    co_np =[]
    for q in range(Q):
        A =list(a)
        #print(A,end=" ")
        if A[abcd[q,1] ] -A[abcd[q,0]] ==abcd[q,2]:
            co_np.append(abcd[q,3])
    ans.append(sum(co_np))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = []
ans = 0
for i in range(Q):
  abcd.append(input())
for X in itertools.combinations_with_replacement(range(1, M + 1), N):
  tmp = 0
  for z in abcd:
    a, b, c, d = map(int, z.split())
    if X[b - 1] - X[a - 1] == c:
      tmp += d
  ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

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

def check(num):
    pre = 0
    for i in range(len(num)):
        if num[i] == 0:
            continue
        if num[i] <= pre:
            return False
        if num[i] > M:
            return False
    else:
        return True

ans = 0
for pattern in range(1 << Q):
    ls = []
    for i in range(Q):
        if pattern & (1 << i):
            ls.append(q[i])
    
    num = [0] * N
    ls = sorted(ls)
    score = 0
    for a, b, c, d in ls:
        if num[a-1] == 0 and num[b-1] == 0:
            num[a-1] = 1
            num[b-1] = c + 1
        elif num[a-1] == 0:
            num[a-1] = num[b-1] - c
        elif num[b-1] == 0:
            num[b-1] = num[a-1] + c
        else:
            if num[b-1] - num[a-1] != c:
                break

        if check(num): score += d
        else: break
    else:
        ans = max(ans, score)

print(ans)

Submission status: Time Limit Exceeded

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

#深さ優先探索により各数列を生成する
As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])

#各数列のスコアを求める
ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0

#スコアの最大値を求める  
ans=max(ls_score+[0])  
print(ans)

Submission status: Time Limit Exceeded

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

#深さ優先探索により各数列を生成する
As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])

#各数列のスコアを求める
ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0

#スコアの最大値を求める  
ans=max(ls_score)  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      array[s+1:] = array[s]
      #for i in range(s+1,0):#以降の項を全て同じ値に
        #array[i] = array[s]
        
  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
    array = next_array(array)#次の配列へ
    
print(max_scr)

Submission status: Time Limit Exceeded

Solution code:
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]
        
  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
    array = next_array(array)#次の配列へ
    
print(max_scr)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0
for i in range(1<<q):
  A=[1]*n
  arrj=[]
  sumd=0
  hantei=True
  for j in range(q):
    if ((i>>j)&1):
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[a-1]!=1 and A[b-1]!=1:
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
      elif A[a-1]==1 and A[b-1]!=1:
        A[a-1]=A[b-1]-c
        if A[a-1]<1:
          hantei=False
          break
      else:
        A[b-1]=A[a-1]+c
        if A[b-1]>m:
          hantei=False
          break
      sumd+=d
      arrj.append(j)
  if hantei:
    for j in arrj:
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[b-1]-A[a-1]!=c:
        hantei=False
        break
  if hantei:
    for j in range(n-1):
      if A[j]>A[j+1]:
        hantei=False
        break
  if hantei and sumd>ans:
    ans=sumd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

A_list = []
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    A_list.append(a)

answer = 0
score_list = []
for A in A_list:
    score = 0
    for i in range(Q):
        a, b, c, d = Q_list[i][0], Q_list[i][1], Q_list[i][2], Q_list[i][3]
        a -=1
        b -=1
        if A[b] - A[a] == c:
            score += d
    answer = max(answer, score)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

A_list = []
for a in itertools.combinations_with_replacement(range(1, M+1), N):
    A_list.append(a)

score_list = []
for A in A_list:
    score = 0
    for i in range(Q):
        a, b, c, d = Q_list[i][0], Q_list[i][1], Q_list[i][2], Q_list[i][3]
        a -=1
        b -=1
        if A[b] - A[a] == c:
            score += d
    score_list.append(score)

print(max(score_list))

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
all_a=[]
def make_a(t):
  ret=[]
  todo=[t]
  while todo:
    i=todo.pop()
    if len(i)==n:
      ret.append(i)
      continue
    for j in range(i[-1],m+1):
      todo.append(i+[j])
  return ret
for i in range(1,m+1):
  all_a.extend(make_a([1]))
ans=0
for an in all_a:
  ansi=0
  for a,b,c,d in abcd:
    if an[b-1]-an[a-1]==c:
      ansi+=d
  ans=max(ans,ansi)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
all_a=[]
def make_a(t):
  if len(t)==n:
    return [t]
  ret=[]
  for ti in range(t[-1],m+1):
    ret.extend(make_a(t+[ti]))
  return ret
for i in range(1,m+1):
  all_a.extend(make_a([1]))
ans=0
for an in all_a:
  ansi=0
  for a,b,c,d in abcd:
    if an[b-1]-an[a-1]==c:
      ansi+=d
  ans=max(ans,ansi)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
abcd=[]
for i in range(q):
  abcd.append(list(map(int,input().split())))
ans=0
for i in range(1<<q):
  A=[1]*n
  sumd=0
  hantei=True
  for j in range(q):
    if ((i>>j)&1):
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[a-1]!=1 and A[b-1]!=1:
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
      elif A[a-1]==1 and A[b-1]!=1:
        A[a-1]=A[b-1]-c
        if A[a-1]<1:
          hantei=False
          break
      else:
        A[b-1]=A[a-1]+c
        if A[b-1]>m:
          hantei=False
          break
      sumd+=d
  if hantei:
    for j in range(q):
      if ((i>>j)&1):
        a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
  if hantei:
    for j in range(n-1):
      if A[j]>A[j+1]:
        hantei=False
        break
  if hantei and sumd>ans:
    ans=sumd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement

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

# n,m,q=3,4,3
# l=[[1,3,3,100], [1,2,2,10], [2,3,2,10]]

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

res=0

for i in range(len(A)):
    tmp=0
    for j in range(len(l)):
        bnum=l[j][1]-1
        anum=l[j][0]-1
        c=l[j][2]
        d=l[j][3]

        if A[i][bnum]-A[i][anum]==c:
            tmp+=d

    res=max(res, tmp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
# n個の数列、1~mの中で数列を作る
n, m, q = map(int, input().split())

comb = combinations_with_replacement(range(1, m + 1), n)
abcd = [list(map(int, input().split())) for _ in [0] * q]

ans = 0
for A in comb:
    cnt = 0
    for i in range(q):
        a, b, c, d = abcd[i][0], abcd[i][1], abcd[i][2], abcd[i][3]
        if A[b - 1] - A[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[]
for i in range(Q):
    tp=tuple(map(int, input().split()))
    ablist.append(tp)
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
print(max(sumlist))