Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
import itertools


def calc(abcd, As, N):
    score = 0
    for a, b, c, d in abcd:
        if As[b-1] - As[a-1] == c:
            score += d
    return score

def solve(N, M, Q, abcd):

    score = 0
    for a1 in range(1, M+1):
        for a2 in range(a1, M+1):
            for a3 in range(a2, M+1):
                for a4 in range(a3, M+1):
                    for a5 in range(a4, M+1):
                        for a6 in range(a5, M+1):
                            for a7 in range(a6, M+1):
                                for a8 in range(a7, M+1):
                                    for a9 in range(a8, M+1):
                                        for a10 in range(a9, M + 1):
                                            score = max(score, calc(abcd, [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10], N))

    return score

if __name__ == "__main__":
    N, M, Q = tuple(map(int, input().split(" ")))
    abcd = []
    for _ in range(Q):
        abcd.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, Q, abcd))

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as comb
n,m,q = map(int,input().split())
ans = 0
query = [[int(i) for i in input().split()] for _ in range(q)]
for A in comb(range(1,m+1),n):
    cnt = 0
    for i in range(q):
        a,b,c,d = query[i]
        if A[b-1]-A[a-1] == c: cnt += d
    ans = max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
n,m,q = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(q)]
com = list(combinations_with_replacement([i+1 for i in range(m)],n))
ans = 0
for combi in com:
    tmp = 0
    for a,b,c,d in Q:
        if combi[b-1]-combi[a-1] == c:
            tmp += d
            ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

for co in combinations_with_replacement(range(1,M+1),N):
    co = sorted(co)
    t=0
    for a,b,c,d in query:
        if co[b-1]-co[a-1]==c:
            t+=d
    ans = max(ans,t)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m,q=map(int,input().split())
A=[tuple(map(int,input().split())) for _ in range(q)]
def pt(X):
  ret=0
  for a,b,c,d in A:
    if X[b-1]-X[a-1]==c:
      ret+=d
  return ret

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

for _ in range(n-1):
  CC=[]
  for c in C:
    for next in range(c[-1],m+1):
      CC.append(c+[next])
  C=CC
ans=0
for c in C:
  ans=max(ans,pt(c))
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for t in itertools.combinations_with_replacement(range(1, M + 1), N):
    tmp = 0
    for a,b,c,d in X:
        if t[b-1] - t[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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


def calc(r):
    res = 0
    for a, b, c, d in check:
        if r[b-1] - r[a-1] == c:
            res += d
    return res


def dfs(t):
    if len(t) == n:
        return calc(t)

    res = [dfs(t + [i]) for i in range(t[-1], m+1)]

    return max(res)


ans = [dfs([i]) for i in range(1, m+1)]

print(max(ans))

Submission status: Accepted

Solution code:

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

ans = 0

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

for i in range(N-1):

    newlis = []
    for j in lis:

        for k in range(j[-1],M+1):
            cp = j.copy()
            cp.append(k)
            newlis.append(cp)

    lis = newlis

ans = 0
abcd = []

for i in range(Q):

    a,b,c,d = map(int,input().split())
    abcd.append([a-1,b-1,c,d])

for A in lis:

    now = 0
    
    for i in range(Q):

        a,b,c,d = abcd[i]

        if A[b] - A[a] == c:
            now += d

    ans = max(ans,now)

print (ans)

Submission status: Accepted

Solution code:
from math import *
from itertools import combinations_with_replacement
ls = []
n, m, q = map(int, input().split())
for i in range(1, m+1):
	ls.append(i)
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)
all_possible = list(combinations_with_replacement(ls, n))
max_score = 0
for each_comb in all_possible:
	combi = list(each_comb)
	score = 0
	for i in range(q):
		if combi[B[i]-1]-combi[A[i]-1] == C[i]:
			score += D[i]
	max_score = max(max_score, score)
print(max_score)

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
ls = []
def dfs(a):
  if len(a) == n:
    ls.append(a)
  else:
    for i in range(a[-1],m+1):
      b = a+[i]
      dfs(b)
for i in range(1,m+1):
  dfs([i])
ans = 0
for x in ls:
  anstmp = 0
  for a,b,c,d in abcd:
    if x[b-1]-x[a-1] == c:
      anstmp += d
  ans = max(anstmp,ans)
print(ans)

Submission status: Accepted

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

    que = [[1]]
    for _ in range(n):
        que2 = []
        for qq in que:
            i = qq[-1]
            for j in range(i, m+1):
                que2.append(qq+[j])
        que = que2

    ans = 0
    for q in que:
        temp = 0
        for a, b, c, d in abcd:
            if q[b]-q[a] == c:
                temp += d
        ans = max(ans, temp)
    print(ans)


main()

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations, combinations_with_replacement
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ll = list(combinations_with_replacement(range(1, M+1), N))
res = 0
for li in ll:
    val = 0
    for abcdi in abcd:
        a, b, c, d = abcdi
        if li[b-1] - li[a-1] == c:
            val += d
    if res < val:
        res = val
print(res)

Submission status: Accepted

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


nums = [k+1 for k in range(M)]
ans = 0
for e in itertools.combinations_with_replacement(nums, N):
    temp = 0
    for f in L:
        a, b, c, d = f[0], f[1], f[2], f[3]
        if e[b-1]-e[a-1] == c:
            temp += d
    ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M, Q = map(int, input().split())
A, B, C, D = [0] * Q, [0] * Q, [0] * Q, [0] * Q
for i in range(Q):
    A[i], B[i], C[i], D[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1


def calc(X):
    score = 0
    for i in range(Q):
        if X[B[i]] - X[A[i]] == C[i]:
            score += D[i]

    return score


def solve(idx, par, X):
    if idx == N:
        return calc(X)

    ret = 0
    for i in range(par, M + 1):
        X[idx] = i
        ret = max(ret, solve(idx + 1, i, X))

    return ret


print(solve(0, 1, [0] * N))

Submission status: Accepted

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

n, m, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(q)]
# global ans0
ans0 = []


def c(L):
    if len(L) == n:
        ans = 0
        for i in range(q):
            if L[A[i][1]-1] - L[A[i][0]-1] == A[i][2]:
                ans += A[i][3]
        ans0.append(ans)
        
    elif len(L) == 0:
        for i in range(1, m+1):
            c([i])
    else:
        for i in range(L[-1], m+1):
            c(L + [i])

c([])
print(max(ans0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, m, q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0

def dfs(s):
    if len(s) == n:
        global ans
        cnt = 0
        for a, b, c, d in abcd:
            a -= 1; b -= 1
            if s[b] - s[a] == c: cnt += d
        ans = max(ans, cnt)
        return
    for i in range(s[-1], m+1):
        dfs(s + [i])

for i in range(1, m+1):
    dfs([i])

print(ans)

Submission status: Accepted

Solution code:
ans = []
def dfs(li):
    if len(li) == n:
        ans.append(li)
        return
    else:
        for i in range(li[-1], m + 1):
            dfs(li + [i])
 
  

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

for i in range(1, m + 1):
   dfs([i])
# print(ans)

res = 0
for ptn in ans:
    tmp = 0
    for a, b, c, d in info:
        a -= 1
        b -= 1
        if ptn[b] - ptn[a] == c:
            tmp += d
    res = max(res, tmp)
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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


def calc_score(A):
    score = 0
    for a, b, c, d in X:
        if A[b - 1] - A[a - 1] == c:
            score += d
    return score


def dfs(A):
    global ans
    if len(A) == N:
        score = calc_score(A)
        ans = max(ans, score)

    elif len(A) == 0:
        for n in range(1, M + 1):
            dfs([n])
    else:
        for n in range(A[-1], M + 1):
            dfs(A + [n])


dfs([])
print(ans)

Submission status: Accepted

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

abcds = [list(map(int,input().split()))for _ in range(q)]
ans = 0
for lis in com(li,n):
    res = 0
    for i in range(q):
        a,b,c,d = abcds[i][0],abcds[i][1],abcds[i][2],abcds[i][3]
        if lis[b-1] - lis[a-1] == c:
            res += d
    ans = max(ans,res)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print('\n'.join(x))

n, m, q = nm()
query = [tuple(nm()) for _ in range(q)]
def dfs(lis):
    if len(lis) >= n:
        yield lis
    else:
        v = 1 if not lis else lis[-1]
        for i in range(v, m+1):
            yield from dfs(lis + [i])

ans = -10**12
E = dfs(list())
for lis in E:
    sc = 0
    for a, b, c, d in query:
        if lis[b-1] - lis[a-1] == c:
            sc += d
    ans = max(ans, sc)
print(ans)

Submission status: Accepted

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

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

P = []
def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])
dfs(1, [])
ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

abcd=[]

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




def score(A):
    retval=0
    for i in range(Q):
        a,b,c,d=abcd[i]
        if A[b-1]-A[a-1]==c:
            retval+=d
    return retval

retval=0
for iter in itertools.combinations_with_replacement([i for i in range(1,M+1)],N):
    retval=max(score(sorted(iter)),retval)

print(retval)

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    res = 0

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

        last_max = 1 if len(A) == 0 else A[-1]

        for i in range(last_max, M+1):
            rec(A + [i])

    rec([])
    print(res)

    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))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, m, q = map(int, input().split())
reqs = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for i in range(1<<(n+m-1)):
	if bin(i).count("1") != n:
		continue
	l = []
	tmp = 1
	for j in range(n+m-1):
		if (i>>j) & 1:
			l.append(tmp)
		else:
			tmp += 1
	res = 0
	for a, b, c, d in reqs:
		if l[b-1] - l[a-1] == c:
			res += d
	ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, q = map(int,input().split())
    ABCD = [None] * q
    for i in range(q):
        a, b, c, d = map(int,input().split())
        ABCD[i] = (a, b, c, d)

    def dfs(A):
        # base case
        if len(A) == n + 1: # score を計算して返す
            # print(A)
            score = 0
            for a, b, c, d in ABCD:
                if A[b] - A[a] == c:
                    score += d
            return score
        # iterate
        res = -INF
        for i in range(A[-1], m + 1):
            res = max(res, dfs(A + [i]))
        return res

    print(dfs([1]))
resolve()

Submission status: Accepted

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

w = [0]*n
res = 0
def dfs(x, y):
    global w, res
    if x == n:
        tmp = 0
        for a, b, c, d in e:
            if w[b-1]-w[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)

Submission status: Accepted

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

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

def dfs(i, A):
    if i == N:
        # calc score
        score = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                score += d
        return score

    ret = 0
    for n in range(A[-1], M+1):
        ret = max(ret, dfs(i + 1, A + [n]))
    return ret

ans = 0
for i in range(1, M+1):
    ans = max(ans, dfs(0, [i]))

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,q = inpm()
    ans = 0
    abcd = []
    for _ in range(q):
        a,b,c,d = inpm()
        abcd.append((a,b,c,d))
    for e in itertools.combinations_with_replacement(range(m),n):
        cnt = 0
        for i in range(q):
            [a,b,c,d] = abcd[i]
            if e[b-1] - e[a-1] == c:
                cnt += d
        ans = max(ans,cnt)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
  a[i], b[i], c[i], d[i] = map(int, input().split())
  a[i] -= 1
  b[i] -= 1

ans = 0
A = [0]*N
def f(p):
  global ans
  if p>=N:
    x = 0
    for i in range(Q):
      if A[b[i]]-A[a[i]]==c[i]:
        x += d[i]
    ans = max(ans, x)
  else:
    for i in range(1 if p==0 else A[p-1], M+1):
      A[p] = i
      f(p+1)
f(0)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(q)]
ans=0
for com in combinations_with_replacement(range(m),n):
	t=0
	for a,b,c,d in L:
		if com[b-1]-com[a-1]==c:
			t+=d
	if t>ans:
		ans=t
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(A):
        res = 0
        for a,b,c,d in g:
            if A[b] == A[a]+c:
                res += d
        return res

    n,m,q = LI()
    g = LIR(q)
    for i in range(q):
        g[i][0] -= 1
        g[i][1] -= 1
    l = [([i],i) for i in range(1,m+1)]
    for i in range(n-1):
        l = [(x+[j], j) for (x,y) in l for j in range(y,m+1)]
    ans = 0
    for A,_ in l:
        s = f(A)
        if ans < s:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

import itertools

ans = 0
for comb in itertools.combinations_with_replacement(list(range(1, m + 1)), n):
    l = list(comb)
    l.sort()
    tmp = 0

    for a, b, c, d in abcd:
        a -= 1
        b -= 1

        if l[b] - l[a] == c:
            tmp += d

    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M,Q=MI()
    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]=MI()
        
    import itertools
    ans=0
    
    
    
    for ite in itertools.combinations_with_replacement(range(1,M+1), N):
        temp=0
        for i in range(Q):
            if ite[b[i]-1]-ite[a[i]-1] == c[i]:
                temp+=d[i]
        ans=max(ans,temp)
        
    print(ans)
    
    
    
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, q = na()
cs = []
for i in range(q):
    cs.append(na())

def dfs(pos, a, m, cs):
    if pos == len(a):
        sc = 0
        for co in cs:
            if a[co[1]-1] - a[co[0]-1] == co[2]:
                sc += co[3]
        return sc

    ans = 0
    low = 1 if pos == 0 else a[pos-1]
    for i in range(low, m+1):
        a[pos] = i
        ans = max(ans, dfs(pos+1, a, m, cs))
    return ans

print(dfs(0, [0] * n, m, cs))

Submission status: Runtime Error

Solution code:
from collections import deque
n,m,q = map(int,input().split())
score = {}
for i in range(1,10):
  for j in range(2,11):
    score[(i,j)] = [0 for k in range(10)]
    
for i in range(q):
  a,b,c,d = map(int,input().split())
  score[(a,b)][c] = d


total = []
dic = {}
for i in range(m):
  dic[(i,)] = score[(1,2)][i]
total.append(dic)

M = []
for i in range(2,n):
  Max = 0
  d = {}
  for k in range(m):
    for tup in total[-1].keys():
      s = total[-1][tup]
      if tup[-1] <= k:
        for j in range(1,i):
          s += score[(j+1,i+1)][k-tup[j-1]] 
        s += score[(1,i+1)][k]  
        ky = tup + (k,)
        d[ky] = s
        if s > Max:
          Max = s
  total.append(d)
  M.append(Max)

print(M[-1])

Submission status: Runtime Error

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

A=[1]
def dfs(y):
    ans=y
    if len(A)==M+1:
        score=0
        for i in range(Q):
            if A[abcd[i][1]]-A[abcd[i][0]]==abcd[i][2]:
                score+=abcd[i][3]
        ans=max(ans,score)
    else:
        x=A[-1]
        for i in range(x,M+1):
            A.append(i)
            ans=dfs(ans)
            A.pop()
    return ans

print(dfs(0))

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(1000000)


def dfs(a):
    if len(a) == n + 1:
        ans = 0
        for i in range(q):
            if int(a[l[i][1]]) - int(a[l[i][0]]) == l[i][2]:
                ans += l[i][3]
        anss.append(ans)
        return

    a += a[-1]
    while int(a[-1]) <= m:
        dfs(a)
        a = list(a)
        a[-1] = str(int(a[-1]) + 1)
        a = "".join(a)


def main():
    n, m, q = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(q)]
    aa = "1"
    anss = []

    dfs(aa)
    print(max(anss))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement

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

for l2 in combinations_with_replacement(range(1,m+1),n):
    total = 0
    for i in range(q):
        if l2[l[i][1] - 1] - l2[l[i][0] - 1] == l[i][2]:
            total += l[i][3]
    ans = max(ans, total)
print(ans)

Submission status: Runtime Error

Solution code:
use proconio::input;
use proconio::marker::Usize1;
use itertools::Itertools;
use std::cmp::max;
fn main() {
    input! {
        n:usize,m:usize,q:usize,
        qs: [(Usize1, Usize1, usize, usize); q]
    };
    let mut ans = 0;
    for A in (1..m+1).combinations_with_replacement(n) {
        let mut sm = 0;
        for &(a,b,c,d) in &qs {
            if A[b]-A[a] == c {
                sm += d;
            }
        }
        ans = max(ans, sm);
    }
    println!("{}", ans);
}

Submission status: Runtime Error

Solution code:
#C - Many Requirements
#再帰関数(n重のfor文)
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
def dfs(A):
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    max_score = 0 
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 1
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
print(dfs[])

Submission status: Runtime Error

Solution code:
k=int(input())
l,r=map(int,input().split())
if(r%k==0 or l%k==0 or r-l>=k):
    print("OK")
else:
    print("NG")

Submission status: Runtime Error

Solution code:
N = int(input())
GACHA=set()
for n in range(N):
  GACHA.add(input())
print(len(GACHA))

Submission status: Runtime Error

Solution code:
N = int(input())
GACHA=[input() for n in range(N)]
print(len(set(GACHA)))

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for t in combinations_with_replacement(range(1, M+1), N):
    an = 0
    for a, b, c, d in ABCD:
        if t[b-1]-t[a-1] == c:
            an += d
    if ans < an:
        ans = an
print(an

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append((int(i) for i in input().strip().split()))


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        try:
            if A[b - 1] - A[a - 1] == c:
                _temp += d
        except BaseException:
            pass
    ans = max(ans, _temp)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:

        if 1 <= a and a < n and 1 <= b and b < n and A[b - 1] - A[a - 1] == c:
            _temp += d
    ans = max(ans, _temp)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    try:
        if res == 0:
            canditates.append(list(cur))
        else:
            for i in range(_min, _max):
                cur.append(i)
                helper(i, _max, cur, res - 1)
                cur.pop()
    except BaseException:
        pass


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            _temp += d
    ans = max(ans, _temp)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            _temp += d
    ans = max(ans, _temp)

print(ans)

Submission status: Runtime Error

Solution code:
n, m, q = [int(i) for i in input().split()]
A = [1] * n
abcd = []

canditates = []

ans = 0

for i in range(q):
    abcd.append([int(i) for i in input().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            _temp += d
    ans = max(ans, _temp)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = np.array([input() for _ in range(n)], dtype=np.float)


ans = 0
temp = a[0]

for i in range(1, n):
    temp = temp * a[i]
    if temp.is_integer():
        ans += 1


print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product

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

temp = list(combinations([i for i in range(1,m+1)],n))


ans = 0

for a_temp in temp:
    ans_temp = 0
    for i in range(q):
        if a_temp[a[i][1]-1] - a_temp[a[i][0]-1] == a[i][2]:
            ans_temp += a[i][3]
    if ans < ans_temp:
        ans = ans_temp
print(ans)