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 sys
sys.setrecursionlimit(10**9)
def solve(n, m, q, A):
  if len(A) == m+1:
    print(A)
    rtn = 0
    for a, b, c, d in q:
      rtn += d if A[b]-A[a] == c else 0
    return rtn
  else:
    return max([solve(n, m, q, A+[i]) for i in range(A[-1], m+1)])

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

Submission status: Runtime Error

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

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

AN = []

for i in range():
  tmp = [0] * N
  AN.append([tmp])

Submission status: Runtime Error

Solution code:
                                                                               │➜  typical
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

import itertools

def main():
  N, M, Q = map(int, input().split())
  all_num = [i for i in range(1, M+1)]
  q_kumi = []
  for i in range(Q):
    q_kumi.append(list(map(int, input().split())))

  ans = 0
  for com in list(itertools.combinations_with_replacement(all_num, N)):
    tmp_ans = 0
    if com != tuple(sorted(com)):
      continue
    for q in q_kumi:
      if com[q[1]-1] - com[q[0]-1] == q[2]:
        tmp_ans += q[3]
    ans = max(ans, tmp_ans)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	ans_list = set()
	for i in list(itertools.product([1,2,3,4,5,6,7,8,9,10],repeat = m)):
		if list(i) == sorted(i):
			for qul in range(q):
				if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2]:
					ans += qu[qul][3]
			ans_list.add(ans)
			ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

def f(nums):
  out=0
  for samp in abcd:
    if nums[samp[1]-1]-nums[samp[0]-1]==samp[2]:
      out+=samp[3]
  return out

def g(nums):
  if nums[-1]<M-1:
    nums[-1]+=1
    return nums, False
  
  i=N-1
  while i>=0 and nums[i]==M-1:
    i-=1
  if i<0:
    return None, True
  
  nums=nums[:i]+[nums[i]+1]*(M-i)
  return nums, False

nums=[0]*N
fi=False
ans=0

while fi==False:
  p=f(nums)
  if ans<p:
    ans=p
  nums, fi=g(nums)
  
print(ans)

Submission status: Runtime Error

Solution code:
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	ans_list = set()
	for i in list(itertools.product([1,2,3,4,5,6,7,8,9,10],repeat = m)):
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2] and list(i) == sorted(i):
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

import itertools
anses = []
# for A in itertools.product(sum(([i]*n for i in range(1,m+1)),[]), repeat=n):

# for A in itertools.product(range(1, m + 1), repeat=n):


def f(i, A):
  for ai in range(A[-1], m + 1):
    if len(A) < m:
      f(ai, A + [ai])
    else:
      p = 0
      for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if A[b] - A[a] == c:
          p += d
      anses.append(p)


f(0, [1])
print(max(anses))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

N=0
M=0

def next_num(x):
    if int(x[-1]) < M:
        return x[:-1] + [int(x[-1]) + 1]
    elif int(x[-1]) == M:
        oya = next_num(x[:-1])
        return oya + [oya[-1]]


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    start = ['1' for i in range(N)]
    current = start
    ans = 0
    while True:
        result = 0
        for a_, b_, c_, d_ in zip(a, b, c, d):
            if int(current[b_]) - int(current[a_]) == c_:
                result += d_
        if result > ans:
            ans = result
        if current[0] == M:
            break
        current = next_num(current)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    global N, M
    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: Runtime Error

Solution code:
import itertools
import numpy as np
N, M, Q = map(int,input().split())
List = [list(map(int, input().split())) for i in range(Q)]

A_full = np.arange(1,M+1)

l_tensu = [0]
for subset in itertools.combinations_with_replacement(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
    
print(max(l_tensu))

Submission status: Runtime Error

Solution code:
import math
n,m,q=map(int,input().split())
qer=[]
for i in range (q):
  a,b,c,d=map(int,input().split())
  qer.append([a,b,c,d])
def calc (a):
  an=0
  for i in range (q):
    if a[qer[i][1]-1]-a[qer[i][0]-1]==e[i][2]:
      an+=qer[i][3]
    return an
ans=[]
def ca(a,i,n,prev):
  if i==n:
    ans.append(calc[a])
  else:
    for j in range (prev,m+1):
      a[i]=j
      ca(a,i+1,n,j)
a=[0]*n
ca(a,0,n,1)
print(max(ans))

Submission status: Runtime Error

Solution code:
import math
n,m,q=map(int,input().split())
qer=[]
for i in range (q):
  a,b,c,d=map(int,input().split())
  qer.append([a,b,c,d])
def calc (a):
  an=0
  for i in range (q):
    if a[qer[i][1]-1]-a[qer[i][0]-1]==e[i][2]:
      an+=qer[i][3]
    return an
ans=[]
def ca(a,i,n,prev):
  if i==n:
    ans.append(calc[a])
  else:
    for j in range (prev,m+1):
      a[i]=j
      ca(a,i+1,n,j)
a=[0]*n
ca(a,0,n,1)
print(math.max(ans))

Submission status: Runtime Error

Solution code:
import itertools

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

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

Alist=[]

for l in itertools.combinations(range(1,n+m-1),n):
    ll=list(l)
    a=[]
    for i in range(n):
        a.append(ll[i]-i)
    Alist.append(a)
slist=[]
for i in range(len(Alist)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if Alist[i][bj-1]-Alist[i][aj-1]==cj:
            s+=dj
    slist.append(s)

print(max(slist))

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(200000)


def read():
    N, M, Q = map(int, input().split())
    ABCD = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        ABCD.append((a, b, c, d))
    return N, M, Q, ABCD


def check(N, M, Q, ABCD, x):
    score = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            score += d
    return score


def solve(N, M, Q, ABCD):
    smax = 0
    for a in range(M+1):
        for b in range(a, M+1):
            for c in range(b, M+1):
                for d in range(c, M+1):
                    for e in range(d, M+1):
                        for f in range(e, M+1):
                            for g in range(f, M+1):
                                for h in range(g, M+1):
                                    for i in range(h, M+1):
                                        for j in range(i, M+1):
                                            s = check(N, M, Q, ABCD, [a, b, c, d, e, f, g, h, i, j][:M])
                                            smax = max(s, smax)
    return smax


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

N=0
M=0

def next_num(x,  M):
    if int(x[-1]) < M:
        return x[:-1] + [int(x[-1]) + 1]
    elif int(x[-1]) == M:
        oya = next_num(x[:-1], M)
        return oya + [oya[-1]]


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    start = ['1' for i in range(N)]
    current = start
    ans = 0
    while True:
        result = 0
        for a_, b_, c_, d_ in zip(a, b, c, d):
            if int(current[b_]) - int(current[a_]) == c_:
                result += d_
        if result > ans:
            ans = result
        if current[0] == M:
            break
        current = next_num(current, M)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Runtime Error

Solution code:
n,m,q=map(int,input().split())
t=[list(map(int,input().split())) for _ in range(q)]
ans=0
import itertools
for p in itertools.permutations(range(1,m+1),m-n):
    a=[]
    for i in range(1,m+1):
        if i not in p:
            a+=[i]
    d=0
    for i in t:
        if a[i[1]-1]-a[i[0]-1]==i[2]:
            d+=i[3]
    ans=max(d,ans)        
print(ans)

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
qer=[]
for i in range (q):
  a,b,c,d=map(int,input().split())
  qer.append([a,b,c,d])
def calc (a):
  an=0
  for i in range (q):
    if a[qer[i][1]-1]-a[qer[i][0]-1]==e[i][2]:
      an+=qer[i][3]
    return an
ans=[]
def ca(a,i,n,prev):
  if i==n:
    ans.append(calc[a])
  else:
    for j in range (prev,m+1):
      a[i]=j
      ca(a,i+1,n,j)
a=[0]*n
ca(a,0,n,1)
print(max(ans))

Submission status: Runtime Error

Solution code:
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	alist = list(itertools.product([1,2,3,4,5,6,7,8,9,10],repeat = m))
	ans_list = set()
	for i in alist:
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2] and list(i) == sorted(i):
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from collections import Counter


def read():
    N, M, Q = map(int, input().split())
    ABCD = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        ABCD.append((a, b, c, d))
    return N, M, Q, ABCD


def check(N, M, Q, ABCD, x):
    score = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            score += d
    return score



def solve(N, M, Q, ABCD):
    smax = 0
    for a in range(M+1):
        for b in range(a, M+1):
            for c in range(b, M+1):
                for d in range(c, M+1):
                    for e in range(d, M+1):
                        for f in range(e, M+1):
                            for g in range(f, M+1):
                                for h in range(g, M+1):
                                    for i in range(h, M+1):
                                        for j in range(i, M+1):
                                            s = check(N, M, Q, ABCD, [a, b, c, d, e, f, g, h, i, j][:M])
                                            smax = max(s, smax)
    return smax


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

N=0
M=0

def next_num(x,  M):
    if x == [str(M)] * N:
        return -1
    if int(x[-1]) < M:
        return x[:-1] + [int(x[-1]) + 1]
    elif int(x[-1]) == M:
        oya = next_num(x[:-1], M)
        return oya + [oya[-1]]


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    start = ['1' for i in range(N)]
    current = start
    ans = 0
    while current[0] != M:
        result = 0
        for a_, b_, c_, d_ in zip(a, b, c, d):
            if int(current[b_]) - int(current[a_]) == c_:
                result += d_
        if result > ans:
            ans = result
        current = next_num(current, M)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Runtime Error

Solution code:
from itertools import combinations

n, m, q = map(int, input().split())
comb = list(combinations(range(1, m+1), n))
ans = [0] * len(comb)
for _ in range(q):
    a, b, c, d = map(int, input().split())
    for i in range(len(comb)):
        if comb[i][b-1] - comb[i][a-1] == c:
            ans[i] += d
print(max(ans))

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
a=[]
b=0
f=[0,0,0]
v=0
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(1):
    for j in range(1,m):
        for z in range(1,m+1):
            f=[int(i),int(j),int(z)]
            for l in range(q):
                
                r=a[l][1]-1
                i=a[l][0]-1
                if int(a[l][2]) == int(f[r] - f[i]):
                    b+=int(a[l][3])
            
            if b>v:
                v=b
            b=0
print(v)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


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

numbers = []
for i in range(Q):
    numbers.append([int(j) for j in input().split()])

numbers = sorted(numbers , key = lambda x:-x[1])
#print(numbers)

kouho = ["9"*(N)]
#print(kouho)
for a, b , c ,d in numbers:
    for k in kouho:
        if int(k[b-1]) - int(k[a-1]) != c:
            new_k = k[:a-1] + str(int(k[b-1])-c) +  k[a:]
            if str(int(k[b-1])-c) >= 0:
                kouho.append(new_k)
                kouho = list(set(kouho))

#print(sorted(kouho))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''
kouho = []
for password in range(0,10**(N-1)):
    password = "9" + str(password).zfill(N-1)
    kouho.append(''.join(list(reversed(password))))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''

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:
def main():
    n,m,q=map(int,input().split())
    a=[]
    b=[]
    c=[]
    d=[]
    ans=0
    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)
    indices = [*range(q)]
    sorted_indices = sorted(indices, key=lambda i: -d[i])
    sorted_num = [d[i] for i in sorted_indices]
    A=[1]*m
    for i in sorted_indices:
        #A[b[i]]-A[a[i]]=c[i]→A[b[i]=c[i]+A[a[i]]
        A[b[i]]=c[i]+A[a[i]]
        if A[b[i]]>m:
            break
        
        #All Check
        tmp=0
        for j in range(q):
            if A[b[j]]-A[a[j]]==c[j]:
                tmp+=d[j]
        ans=max(ans,tmp)
    print(ans)
    
    

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


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

numbers = []
for i in range(Q):
    numbers.append([int(j) for j in input().split()])

numbers = sorted(numbers , key = lambda x:-x[1])
#print(numbers)


kouho = ["9"*(N)]
#print(kouho)
for a, b , c ,d in numbers:
    for k in kouho:
        if int(k[b-1]) - int(k[a-1]) != c:
            #Eprint(k[a-1:] , k[:a-1])
            new_k = k[:a-1] + str(int(k[b-1])-c) +  k[a:]
            kouho.append(new_k)
            kouho = list(set(kouho))

#print(sorted(kouho))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''
kouho = []
for password in range(0,10**(N-1)):
    password = "9" + str(password).zfill(N-1)
    kouho.append(''.join(list(reversed(password))))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''

Submission status: Runtime Error

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

Submission status: Runtime Error

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

A_full = np.arange(1,M+1)

l_tensu = [0]
for subset in itertools.combinations(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
    
print(max(l_tensu))

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
value = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    value.append([a - 1, b - 1, c, d])
value.sort()
ans_list = []
for i in range(2 **q):
    t = '0' * (q - len(bin(i)[2:])) + bin(i)[2:]
    dp = [1] * m
    dp_k = [0] * m
    ans = 0
    for j, tt in enumerate(t):
        if tt == '1':
            if dp_k[value[j][1]] == 0:
                dp[value[j][1]] = dp[value[j][0]] + value[j][2]
                dp_k[value[j][1]] = 1
                if dp[value[j][1]] <= m:
                    ans += value[j][3]
                else:
                    ans = 0
                    break
            elif dp_k[value[j][1]] == 1:
                if dp[value[j][1]] == dp[value[j][0]] + value[j][2]:
                    ans += value[j][3]
                else:
                    ans = 0
                    break
            else:
                ans = 0
                break
    ans_list.append(ans)
print(max(ans_list))

Submission status: Runtime Error

Solution code:
N, M, Q = map(int,input().split())
List = [list(map(int, input().split())) for i in range(Q)]
A_full = np.arange(1,M+1)

l_tensu = [0]
for subset in itertools.combinations(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
   
  
print(max(l_tensu))

Submission status: Runtime Error

Solution code:
N, M, Q = list(map(int, input().split()))
A = []
B = []
C = []
D = []

for i in range(Q):
    a,b,c,d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)


ANS = []

import itertools
for i in itertools.product(range(1,M+1), repeat=N):
    f = 0
    for j in range(len(i)-1):
        if not i[j] < i[j+1]:
            f=1
    if f == 0:
        #print(i)
        ans = 0
        for q in range(Q):
            if i[B[q]-1] - i[A[q]-1] == C[q]:
                ans += D[q]
        ANS.append(ans)
print(max(ANS))

Submission status: Runtime Error

Solution code:
import itertools
N, M, Q = map(int,input().split())
List = [list(map(int, input().split())) for i in range(Q)]
l_tensu = [0]
for subset in itertools.combinations(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
print(max(l_tensu))

Submission status: Runtime Error

Solution code:
n, mm, q = map(int,input().split())
a, b, c, d = [0]*q, [0]*q, [0]*q, [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
import itertools
td = []
ttd = []

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

s = list(itertools.combinations(m, n))
for j in range(len(s)):
    for i in range(q):
        if s[j][b[i]-1] - s[j][a[i]-1] == c[i]:
            td.append(d[i])
    ttd.append(sum(td))
    td = []
print(max(ttd))

Submission status: Runtime Error

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

for i in range(Q):
  if judge == True:
    score += P[i][3]
  scores.append(score)
  
print(max(scores))

Submission status: Runtime Error

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    data = range(1, M+1)
    A = []
    for i in range(len(data)):
        for j in range(i, len(data)):
            for k in range(j, len(data)):
                A.append([data[i], data[j], data[k]])
    l = []
    m = 0
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        l.append([a, b, c, d])
    for a_list in A:
        tmp = 0
        for i in l:
            if a_list[i[1] -1] - a_list[i[0] - 1] == i[2]:
                tmp += i[3]
        if tmp > m:
            m = tmp
    return m


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

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

import itertools
from collections import defaultdict

seq = list(range(1, M+1))
dlist = defaultdict(list)
dres  = defaultdict(int)
Na    = 0

for i,v in enumerate(itertools.combinations(seq, N)):
    dlist[i] = v
    Na += 1

#print(seq)
#print(dlist)

#import numpy as np

#X = np.r_[[dlist[i] for i in range(Na)]]

#Y = np.zeros((Q, 4), dtype=int)

for i in range(Q):
    ai, bi, ci, di = map(int, input().split())
    #Y[i] = [ai, bi, ci, di]
    #print(ai-1, bi-1, ci, di)
    for j in range(Na):
        tmp = dlist[j]
        if tmp[bi-1] - tmp[ai-1] == ci:
            dres[j] += di
print(max([dres[i] for i in range(Na)]))

Submission status: Runtime Error

Solution code:

import itertools

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


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

choices = list(itertools.combinations_with_replacement([i for i in range(1, m+1)], n))
ans = -1
for choice in choices:
    score = 0
    for q in query:
        if choice[q[1]-1] - choice[q[0]-1] == q[2]:
            score += q[3]
    ans = max(ans, score)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools

def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    data = range(1, M+1)
    A = []
    for i in range(len(data)):
        for j in range(i, len(data)):
            for k in range(j, len(data)):
                A.append([data[i], data[j], data[k]])
    l = []
    m = 0
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        l.append([a, b, c, d])
    for a_list in A:
        tmp = 0
        for i in l:
            if a_list[i[1] -1] - a_list[i[0] - 1] == i[2]:
                tmp += i[3]
        if tmp > m:
            m = tmp
    return m


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
def resolve():
    n, m, q = map(int, input().split())
    queue = []
    for i in range(q):
        queue.append(list(map(int, input().split())))
    ans = 0
    import itertools
    l = list(itertools.combinations(range(1, n + m), m))
    for i in l:
        a = [x - y for y, x in enumerate(i)]
        x = 0
        for j in queue:
            if a[j[1] - 1] - a[j[0] - 1] == j[2]:
                x += j[3]
        ans = max(ans, x)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
A,B,N = map(int,input().split())
#N=int(input())
#A = list(map(int,input().split()))
#S=str(input())
m=0
if B<N:
    N=B
s=int(B/A)
if s>N:
    print(0)
    exit()
for x in range(s,N+1,s):
    num=int(A*x/B) - A * int(x/B)

    m=max(num,m)

print(m)

Submission status: Runtime Error

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

A = [0]*N
A[0] = 1
MAX = 0
for i1 in range(1,11):
  A[1] = i1
  if N==2:
    S = 0
    for i in range(Q):
      if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
        S += l[i][3]
        if S>MAX:
          MAX = S
          continue
  for i2 in range(i1,11):
    A[2] = i2
    if N==3:
      S = 0
      for i in range(Q):
        if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
          S += l[i][3]
          if S>MAX:
            MAX = S
      continue
    for i3 in range(i2,11):
      A[3] = i3
      if N==4:
        S = 0
        for i in range(Q):
          if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
            S += l[i][3]
            if S>MAX:
              MAX = S
        continue
      for i4 in range(i3,11):
        A[4] = i4
        if N==5:
          S = 0
          for i in range(Q):
            if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
              S += l[i][3]
              if S>MAX:
                MAX = S
          continue
        for i5 in range(i4,11):
          A[5] = i5
          if N==6:
            S = 0
            for i in range(Q):
              if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
                S += l[i][3]
                if S>MAX:
                  MAX = S
            continue
          for i6 in range(i5,11):
            A[6] = i6
            if N==7:
              S = 0
              for i in range(Q):
                if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
                  S += l[i][3]
                  if S>MAX:
                    MAX = S
              continue
            for i7 in range(i6,11):
              A[7] = i7
              if N==8:
                S = 0
                for i in range(Q):
                  if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
                    S += l[i][3]
                    if S>MAX:
                      MAX = S
                continue
              for i8 in range(i7,11):
                A[8] = i8
                if N==9:
                  S = 0
                  for i in range(Q):
                    if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
                      S += l[i][3]
                      if S>MAX:
                        MAX = S
                  continue
                for i9 in range(i8,11):
                  A[9] = i9
                  S = 0
                  for i in range(Q):
                    if A[l[i][1]-1]-A[l[i][0]-1]==l[i][2]:
                      S += l[i][3]
                  if S>MAX:
                    MAX = S
print(MAX)

Submission status: Runtime Error

Solution code:
import itertools
N, M, Q = map(int, input().split())
a = [list(map(int, input().split())) for l in range(Q)]
b = [1]*N
c = 0
for i in range(Q):
  if b[a[i][2]-1]-b[a[i][1]-1] == a[i][3]:
    c += a[i][4]
C = c
for k in range(1,M):
  nums = [i for i in range(N-1)]
  for balls in itertools.combinations_with_replacement(nums, k):
    b = [1]*N
    c = 0
    for i in range(1,N):
      b[i] = b[i-1] + balls.count(i-1)
    for i in range(Q):
      if b[a[i][1]-1]-b[a[i][0]-1] == a[i][2]:
        c += a[i][3]
    C = max(C,c)
print(C)