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: Runtime Error

Solution code:
import itertools
N, M ,Q = map(int, input().split())
l = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  l.append([a, b, c, d])
  
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
nums = list(itertools.combinations_with_replacement(num, 10))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]]-row[l[i][0]] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(10)]
for i in range(10):
  for j in range(i,10):
    for k in range(j,10):
      for l in range(k,10):
        for m in range(l,10):
          for n in range(m,10):
            for o in range(n,10):
              for p in range(o,10):
                for q in range(p,10):
                  for r in range(q,10):
                    A[0]=i
                    A[1]=j
                    A[2]=k
                    A[3]=l
                    A[4]=m
                    A[5]=n
                    A[6]=o
                    A[7]=p
                    A[8]=q
                    A[9]=r
                    su=0
                    for z in range(Q):
                      if A[b[z]]-A[a[z]]==c[z]:
                        su+=d[z]
                    if su>maxs:
                      maxs=su
print(maxs)

Submission status: Runtime Error

Solution code:
import itertools
N, M ,Q = map(int, input().split())
l = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  l.append([a, b, c, d])
  
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
nums = list(itertools.combinations_with_replacement(nums, 10))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]]-row[l[i][0]] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M, Q = mi()
abcd = li2(Q)

'''
a = '0' * N
m = str(M-1)
l = [a]

while True:
    i = N-1
    while i >= 0 and a[i] == m:
        i -= 1
    if i == -1:
        break
    a = list(a)
    num = str(int(a[i]) + 1)
    a[i] = num
    if i != N-1:
        for j in range(i+1, N):
            a[j] = num
    tmp = ''.join(a)
    l.append(tmp)
'''

def dfs(num, length):
    if length == N:
        l.append(num)
        return
    last = int(num[-1])
    for i in range(last, M):
        dfs(num + str(i), length+1)

dfs('0', 1)
ans = 0
for num in l:
    cnt = 0
    num = list(map(int, list(num)))
    for i in range(Q):
        if num[abcd[i][1]-1] - num[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(10)]
for i in range(10):
  for j in range(i,10):
    for k in range(j,10):
      for l in range(k,10):
        for m in range(l,10):
          for n in range(m,10):
            for o in range(n,10):
              for p in range(o,10):
                for q in range(p,10):
                  for r in range(q,10):
                    A[0]=i
                    A[1]=j
                    A[2]=k
                    A[3]=l
                    A[4]=m
                    A[5]=n
                    A[6]=o
                    A[7]=p
                    A[8]=q
                    A[9]=r
                    su=0
                    for z in range(Q):
                      if A[b[z]+1]-A[a[z]+1]==c[z]:
                        su+=d[z]
                    if su>maxs:
                      maxs=su
print(maxs)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools


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

vals = []
for i in range(Q):
    vals.append([list(map(int, input().split(" ")))])
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())   
a = []
for i in range(10):
  a.append(1)
max = 0
inp = []
for i in range(q):
  ta,tb,tc,td = map(int,input().split())
  inp.append((ta,tb,tc,td))
for i1 in range(1,m+1):
  a[0] = i1
  for i2 in range(i1,m+1):
    a[1] = i2
    for i3 in range(i2,m+1):
      a[2] = i3
      for i4 in range(i3,m+1):
        a[3] = i4
        for i5 in range(i4,m+1):
          a[4] = i5
          for i6 in range(i5,m+1):
            a[5] = i6
            for i7 in range(i6,m+1):
              a[6] = i7
              for i8 in range(i7,m+1):
                a[7] = i8
                for i9 in range(i8,m+1):
                  a[8] = i9
                  for i10 in range(i9,m+1):
                    a[9] = i10
                    sum = 0
                    for i in range(q):
                      if a[inp[i][1]] - a[inp[i][0]] == inp[i][2]:
                        sum = sum + inp[i][3]
                      if sum > max:
                        max = sum

print(max)

Submission status: Runtime Error

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

n, m, q = [int(x) for x in input().split()]
abcd = [[int(x) for x in input().split()] for _ in range(q)]
all_pattern = []
start = '1'
def dfs(s):
    last_s = int(s[-1])
    next_s = [str(x) for x in range(last_s, m + 1)]
    for i in next_s:
        t = s + i
        if len(t) == n + 1:
            all_pattern.append(t[1:])
        else:
            dfs(t)
dfs(start)
ans = 0
for pattern in all_pattern:
    res = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if int(pattern[b - 1]) - int(pattern[a - 1]) == c:
            res += d
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
mport itertools
 
N, M, Q = map(int, input().split())
cmb = [list(map(int, input().split())) for _ in range(Q)]
 
def score(seq):
  s = 0
  for q in range(Q):
    if seq[cmb[q][1]-1] - seq[cmb[q][0]-1] == cmb[q][2]:
      s += cmb[q][3]
  return s
 
p = [i for i in range(1, M+1)]
A = itertools.combinations_with_replacement(p, N)
ans = 0
for a in A:
  ans = max(ans, score(a))
print(ans)

Submission status: Runtime Error

Solution code:
mport itertools
 
N, M, Q = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(Q)]
 
def score(seq):
  s = 0
  for q in range(Q):
    if seq[c[q][1]-1] - seq[c[q][0]-1] == c[q][2]:
      s += c[q][3]
  return s
 
p = [i for i in range(1, M+1)]
A = itertools.combinations_with_replacement(p, N)
ans = 0
for a in A:
  ans = max(ans, score(a))
print(ans)

Submission status: Runtime Error

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 = [1] * 10

def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]] - A[a[i]] == c[i]:
      t += d[i]
  if ans < t:
    return t
  else:
    return ans

ans = 0
for i1 in range(1, m):
  A[1] = i1
  for i2 in range(i1, m):
    A[2] = i2
    for i3 in range(i2, m):
      A[3] = i3
      for i4 in range(i3, m):
        A[4] = i4
        for i5 in range(i4, m):
          A[5] = i5
          for i6 in range(i5, m):
            A[6] = i6
            for i7 in range(i6, m):
              A[7] = i7
              for i8 in range(i7, m):
                A[8] = i8
                for i9 in range(i8, m):
                  A[9] = i9
                  ans = check(A, ans)
print(ans)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(10)]
for i in range(10):
  for j in range(i,10):
    for k in range(j,10):
      for l in range(k,10):
        for m in range(l,10):
          for n in range(m,10):
            for o in range(n,10):
              for p in range(o,10):
                for q in range(p,10):
                  for r in range(q,10):
                    A[0]=i
                    A[1]=j
                    A[2]=k
                    A[3]=l
                    A[4]=m
                    A[5]=n
                    A[6]=o
                    A[7]=p
                    A[8]=q
                    A[9]=r
                    su=0
                    for i z in range(Q):
                      if A[b[i]]-A[a[i]]==c[i]:
                        su+=d[i]
                    if su>maxs:
                      maxs=su
print(maxs)

Submission status: Runtime Error

Solution code:
A, B, N = map(int, input().split())
S =[]
 
for x in range(0,N):
  c = int(A*x/B)
  d = int(x/B)
  D = D * A
  E = C-D
  S.append(E)
  
print(max(S))

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
for i in range(10):
  for j in range(i,10):
    for k in range(j,10):
      for l in range(k,10):
        for m in range(l,10):
          for n in range(m,10):
            for o in range(n,10):
              for p in range(o,10):
                for q in range(p,10):
                  for r in range(q,10):
                    A[0]=i
                    A[1]=j
                    A[2]=k
                    A[3]=l
                    A[4]=m
                    A[5]=n
                    A[6]=o
                    A[7]=p
                    A[8]=q
                    A[9]=r
                    su=0
                    for i z in range(Q):
                      if A[b[i]]-A[a[i]]==c[i]:
                        su+=d[i]
                    if su>maxs:
                      maxs=su
print(maxs)

Submission status: Runtime Error

Solution code:
import itertools

n,m,q = input().split()
n = int(n)
m = int(m)
q = int(q)
num_list = []
a = list(range(1, n+1))
for i in range(q):
    num_list.append(list(map(int,input().split())))
ff = list(itertools.combinations_with_replacement(a, m))
max = 0
for i in range(len(ff)):
  s = 0
  for j in range(q):
    a,b,c,d = num_list[j]
    if ff[i][b-1] - ff[i][a-1] == c:
      s = s + d
  if max < s:
        max = s
print(max)

Submission status: Runtime Error

Solution code:
ALL=[]
ma=0
v=[1]*10
def f(idx):
    global ma,v,N,M
    if(idx==N):
        score=0
        for i in range(Q):
            if(v[A[i]]-v[B[i]]==C[i]):
                score+=D[i]
        if ma<score:
            ma=score
        return
    for i in range(v[idx-1],M):
        v[idx]=i
        f(idx+1)
N,M,Q= list(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]=list(map(int, input().split()))
f(1)
print(ma)

Submission status: Runtime Error

Solution code:
import itertools
 
N,M,Q=map(int,input().split())
all=[]
for i in range(Q):
  all.append(list(map(int,input().split()))
 
x=[i for i in range(1,M+1)]
maxdsum=0
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

Submission status: Runtime Error

Solution code:
import itertools

n,m,q = input().split()
n = int(n)
m = int(m)
q = int(q)
num_list = []
a = list(range(1, n+1))
for i in range(q):
    num_list.append(list(map(int,input().split())))
num_list = sorted(num_list, reverse=True, key=lambda x: x[3])
ff = list(itertools.combinations_with_replacement(a, m))
max = 0
for i in range(len(ff)):
  s = 0
  for j in range(q):
    a,b,c,d = num_list[j]
    if ff[i][b-1] - ff[i][a-1] == c:
      s = s + d
  if max < s:
        max = s
print(max)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
a=[0 for i in range(Q)]
b=[0 for i in range(Q)]
c=[0 for i in range(Q)]
d=[0 for i in range(Q)]
A=[0 for i in range(N)]
def swap(a,b,c):
    kari=a[b]
    a[b]=a[c]
    a[c]=kari
    return a
for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int, input().split())
for i in range(0,N):
    if(N==1):
        break
    for j in range(1,N-i):
        if d[j]>d[j-1]:
            d=swap(d,j,j-1)
            a=swap(a,j,j-1)
            b=swap(b,j,j-1)
            c=swap(c,j,j-1)
sum=0
recode={}
for i in range(0,Q):
    if a[i] in recode.keys() and b[i] in recode.keys():
        continue
    else:
        recode[a[i]]=1
        recode[b[i]]=1
        sum+=d[i]
print(sum)

Submission status: Runtime Error

Solution code:
import itertools
 
N,M,Q=map(int,input().split())
all=[]
 
for i in range(Q):
  all.append(list(map(int,input().split())))
#print(all)
#print(len(all))
#print(all[0][1])
 
x=sorted([i for i in range(1,M+1)])
maxdsum=0
 
 
for A in itertools.combinations_with_replacement(x, N):
  dsum=0
  "print("A=="+str(A))
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

Submission status: Runtime Error

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

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

amount = 0
max_amount = 0
for i in range(number): #A
    
    for j in range(Q): # P
        bi = P[j][1]
        ai = P[j][0]
        if(A[i][bi-1] - A[i][ai-1] == P[j][2]):
            amount += P[j][3]
        
   # print(amount)
    
   # print(amount)
    if(amount >= max_amount):
        max_amount = amount
    
    amount = 0
    
print(max_amount)

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement as comb

n,m,q = map(int, input().split(' '))
lis = [list(map(int, input().split())) for _ in range(q)]
tes = comb(range(1,m))
res = 0
for i in tes:
    te = 0
    for a,b,c,d in lis:
        if c == i[b-1] - i[a-1]:
            te += d
    res = max(te,res)
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

n, m, q = map(int, input().split())
a = np.zeros(q, type=int)
b = np.zeros(q, type=int)
c = np.zeros(q, type=int)
d = np.zeros(q, type=int)

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

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

Submission status: Runtime Error

Solution code:

n,m,q = map(int,input().split())
num_lst = []
for i in range(q):
    num_lst.append(list(map(int,input().split())))
l = list(range(1,m+1))
A = list(combinations_with_replacement(l,n))

mx = 0
for now_A in A:
    score = 0
    for nums in num_lst:
        a,b,c,d = nums
        if now_A[b-1] - now_A[a-1] == c:
            score += d
    mx = max(mx,score)
print(mx)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
check = list()
for i in range(Q):
  check.append(list(map(int, input().split())))
ans = 0

for i1 in range(1, M+1):
  for i2 in range(i1, M+1):
    for i3 in range(i2, M+1):
      for i4 in range(i3, M+1):
        for i5 in range(i4, M+1):
          for i6 in range(i5, M+1):
            for i7 in range(i6, M+1):
              for i8 in range(i7, M+1):
                for i9 in range(i8, M+1):
                  L = [1, i1, i2, i3, i4, i5, i6, i7, i8, i9]
                  A = list()
                  for i in range(M):
                    A.append(L[i])
                  tmp = 0
                  for i in range(Q):
                    a = check[i][0]
                    b = check[i][1]
                    c = check[i][2]
                    d = check[i][3]
                    if(A[b-1]-A[a-1] == c):
                      tmp += d
                  ans = max(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m,q=list(map(int,input().split()))
q_l=[list(map(int,input().split())) for _ in range(q)]
#print(q_l)
#bar_l = [(i,j,k) for i in range(0,m+1) for j in range(i,m+1) for k in range(j,m+1)]
bar_m = [i for i in range(m)]
#print(bar_m)
bar_l = list(itertools.combinations_with_replacement(bar_m,m))
#print(bar_l)
score = 0
for bar in bar_l:
    score_tmp=0
    for queue in q_l:
        if bar[queue[1]-1]-bar[queue[0]-1]==queue[2]:
            score_tmp+=queue[3]
    #print(score_tmp)
    if score<score_tmp:
        score=score_tmp
print(score)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

from itertools import combinations_with_replacement as CwR



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

Tables = list(CwR(range(1,M+1),N))
Sum_cor = []
for Table in Tables:
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)


print(max(Sum_cor))

Submission status: Runtime Error

Solution code:
import sys
input = readline
from itertools import product

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

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

kumiawase = list(product(range(1, m + 1), repeat=n))

ans = 0
for kumi in kumiawase:
    A = [0] + list(kumi)
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if A[b] - A[a] == c:
            temp += d
    ans = max(ans, temp)

print(ans)

Submission status: Runtime Error

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

A = []


def dfs(num):
    if len(str(num)) == n:
        A.append(num)
    else:
        now = int(str(num)[-1])
        for i in range(now, m + 1):
            dfs(int(str(num) + str(i)))


for i in range(1, 10):
    dfs(i)

ans = 0
for i in range(len(A)):
    now = str(A[i])
    point = 0
    for j in range(q):
        a, b, c, d = abcd[j]
        a -= 1
        b -= 1
        if int(now[b]) - int(now[a]) == c:
            point += d

    ans = max(ans, point)

print(ans)

Submission status: Runtime Error

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

A = itertools.combinations_with_replacement([i for i in range(1,M+1)], N)
count = []
for a in A:
    temp = 0
    for l in l:
        if a[l[1]-1] - a[l[0]-1] == l[2]:
            temp += l[3]
    count.append(temp)
print(max(count))

Submission status: Runtime Error

Solution code:
from collections import deque

def solve(n, m, q, A):
  if len(A) == m+1:
    rtn = 0
    for b, v in q.items():
      if v:
        for a, c, d in v:
          rtn += d if A[b]-A[a] == c else 0
    return rtn
  else:
    rtn = 0
    xs = []
    for i in range(A[-1], m+1):
      b = len(A)
      for a, c, _ in q[b]:
        if i-A[a] == c:
          xs.append(i)
    return max([solve(n, m, q, A+[x]) for x in (set(xs) if xs else range(A[-1], m+1))])

N, M, Q = map(int, input().split())
dic = {i:[] for i in range(1, M+1)}
for _ in range(Q):
  a, b, c, d = map(int, input().split())
  dic[b].append((a, c, d))
ans = 0
q = deque()
q.append([1])
while q:
  A = q.pop()
  if len(A) == N+1:
    rtn = 0
    for b, v in dic.items():
      if v:
        for a, c, d in v:
          rtn += d if A[b]-A[a] == c else 0
    ans = max(rtn, ans)
  else:
    for i in range(A[-1], M+1):
      b = len(A)
      if dic[b]:
        for a, c, d in dic[b]:
          if i-A[a] == c:
            q.append(A+[i])
      else:
        q.append(A+[i])
print(ans)

Submission status: Runtime Error

Solution code:

list = [0]*Q
res = 0


def solve():

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

    def dfs(x, y):
        global list, res
        if x == N:
            tmp = 0
            for a, b, c, d in e:
                if list[b-1]-list[a-1] == c:
                    tmp += d
            res = max(res, tmp)
            return

        for i in range(y, M+1):
            w[x] = i
            dfs(x+1, i)

    dfs(0, 1)
    print(res)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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

import sys
import itertools

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


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

    l = [i for i in range(1, m)]
    combi_list = list(itertools.combinations_with_replacement(l, n))

    ans_dic = {}
    for combi in combi_list:
        ans_dic[str(combi)] = 0

    for combi in combi_list:

        for i, a_d in enumerate(a_d_list):
            a = a_d[0]
            b = a_d[1]
            c = a_d[2]
            d = a_d[3]

            if combi[b-1] - combi[a-1] == c:

                ans_dic[str(combi)] += d


    print(max(ans_dic.values()))





if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from itertools import combinations
n,m,q = map(int, input().split())
tmp_A = [i+1 for i in range(m)]

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

top = 0    
import itertools
it = itertools.combinations_with_replacement(tmp_A, n)
for base in list(it):
    for i in range(len(SU)):
        e,f,g,h = SU[i][0], SU[i][1], SU[i][2], SU[i][3]
        if e-1 <= len(base) and f-1 <= len(base):
            if (base[f-1] - base[e-1]) == g:
                res += h
            if res >= top:
                top = res         
print(top)

Submission status: Runtime Error

Solution code:
from itertools import combinations
n,m,q = map(int, input().split())
tmp_A = [i+1 for i in range(m)]

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

top = 0    
import itertools
it = itertools.combinations_with_replacement(tmp_A, n)
for base in it:
    for i in range(len(SU)):
        e,f,g,h = SU[i][0], SU[i][1], SU[i][2], SU[i][3]
        if e-1 <= len(base) and f-1 <= len(base):
            if (base[f-1] - base[e-1]) == g:
                res += h
            if res >= top:
                top = res         
print(top)

Submission status: Runtime Error

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_list = []
for p in itertools.combinations_with_replacement(range(1,m+1),n):
    A_list.append(p)
# print(A_list)

ans = 0
for v in A_list:
    cur_score = 0
    for i in range(q):
        if v[b[i]-1] - v[a[i]-1] == c[i]:
            cur_score += d[i]
    ans = max(ans,cur_score)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import time


def make_table(n, m):
    Table = np.random.randint(1,m+1)
    return Table

t0 = time.time()
n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Sum_cor = []
for i in range(10000000000):
    Table = make_table(n,m)
    Table.sort()
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)
    t1 = time.time()
    if t1-t0 >1.88:
        print(max(Sum_cor))
        break

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import time


def make_table(n, m):
    Table = np.random.randint(1,m+1)
    return Table

t0 = time.time()
n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Sum_cor = []
for i in range(10000000000):
    if m >=6:
        Table = make_table(n,m)
    else:
        Table = make_table(n,m)
    Table.sort()
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)
    t1 = time.time()
    if t1-t0 >1.9:
        print(max(Sum_cor))
        print(i)
        break

Submission status: Runtime Error

Solution code:
import itertools

N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
res = 0
ls=list(range(1,M+1))

for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]]-a[c[0]]==c[2]:
            p += c[3]
        res = max(res,p)

print(res)

Submission status: Runtime Error

Solution code:
N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
import itertools
res = 0
ls=list(range(1,M+1))
for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]]-a[c[0]]==c[2]:
            p += c[3]
        res = max(res,p)
print(res)

Submission status: Runtime Error

Solution code:
# 2020/05/02
# AtCoder Beginner Contest 165 - C

a = list()
def mkArray(in_list, sav_val, cnt):
    if cnt >= m:
        a.append(in_list)
        return 0
    else:
        for x in range(sav_val, m + 1):
            wk_list = list()
            wk_list.extend(in_list)
            wk_list.append(x)
            mkArray(wk_list, x, cnt + 1)

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

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

# Make Array
w_a = list()
mkArray(w_a, 1, 0)

# Search
ans = 0
for i in range(len(a)):
    wans = 0
    for j in range(q):
        if a[i][abcd[j][1]-1] - a[i][abcd[j][0]-1] == abcd[j][2]:
            wans = wans + abcd[j][3]

    if wans > ans:
        ans = wans

# Output
print(ans)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(q)]
b = []
for i in range(m):
    b.append(i+1)
import itertools
l = list(itertools.combinations_with_replacement(b,n))
max=0
from math import factorial
c = factorial(m) / factorial(n) / factorial(m - n)
#print(l)                                                                      

#for _ in range(int(c)):                                                       
for ll in l:
    m=0
#    print(ll)                                                                 
    for aa in a:
#        print(ll[aa[1]-1],ll[aa[0]-1],aa[2])                                  
        if ll[aa[1]-1]-ll[aa[0]-1]==aa[2]:
 #           print(aa[3])                                                      
            m+=aa[3]
    if max < m:
        max=m
  #  print(m,max)                                                              
print(max)

Submission status: Runtime Error

Solution code:
from collections import deque
de = deque()
n,m,q = map(int,input().split())
queries = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    queries.append((a,b,c,d))
de.append([1])
maxscore = 0
while de: 
    li = de.popleft()
    if len(li) < m:
        for i in range(li[-1],11):
            new_li = li + [i]
            de.append(new_li)
    else:
        score = 0
        for i in range(q):
            a,b,c,d = queries[i]
            if li[b-1]-li[a-1] == c:
                score += d
        maxscore = max(maxscore,score)
print(maxscore)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
a = []
for i in range(m-1):
    a.append(list(map(int,input().split())))
d = []
for i in range(m-1):
    d.append(a[i][3])

dd = sorted(d,reverse = True)[:q-1]
print(sum(dd))

Submission status: Runtime Error

Solution code:
# 2020/05/02
# AtCoder Beginner Contest 165 - C

a = list()
def mkArray(in_list, sav_val, cnt):
    if cnt >= m - 1:
        a.append(in_list)
        return 0
    else:
        for x in range(sav_val, m + 1):
            wk_list = list()
            wk_list.extend(in_list)
            wk_list.append(x)
            mkArray(wk_list, x, cnt + 1)

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

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

# Make Array
w_a = list()
mkArray(w_a, 1, 0)

# Search
ans = 0
for i in range(len(a)):
    wans = 0
    for j in range(q):
        if a[i][abcd[j][1]-1] - a[i][abcd[j][0]-1] == abcd[j][2]:
            wans = wans + abcd[j][3]

    if wans > ans:
        ans = wans

# Output
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

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

m_list = [i for i in range(1, M + 1)]
# print(m_list)
all_sequence_list = list()
score_list = list()
for sequence in itertools.combinations(m_list, N):
    # print(sequence)
    score_tmp = 0
    for ai, bi, ci, di in int_tuple_list:
        if ci == sequence[bi - 1] - sequence[ai - 1]:
            score_tmp += di

    # print(score_tmp)
    score_list.append(score_tmp)

print(max(score_list))

Submission status: Runtime Error

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

import numpy as np
import itertools
A_ = np.arange(1,m+1)
A_list = []
res = 0
for x in itertools.product(A_, repeat=len(A_)):
    tmp = list(x)
    tmp.sort()
    if tmp not in A_list:    
        A_list.append(tmp)
    
for A in  A_list:
    tmp2 = 0
    for ss in s:
        sss =  A[ss[1]] - A[ss[0]] - ss[2]
        if sss == 0:
            tmp2 += ss[3]
    if tmp2 > res:
        res = tmp2
print(res)