Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Time Limit Exceeded

Solution code:
def combinations_with_replacement(elements, N):
    for element in elements:
        if N == 1:
            yield [element]
        else:
            for combination in combinations_with_replacement(elements, N-1):
                if element >= combination[-1]:
                    yield combination + [element]


N, M, Q = map(int, input().split())
a = [None for _ in range(Q)]
b = [None for _ in range(Q)]
c = [None for _ in range(Q)]
d = [None for _ in range(Q)]
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

ans = 0
elements = list(range(1, M+1))
for combination in combinations_with_replacement(elements, N):
    score = 0
    for i in range(Q):
        if combination[b[i]-1] - combination[a[i]-1] == c[i]:
            score += d[i]
    ans = max(score, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

first = sys.stdin.readline().strip().split()
N = int(first[0])  # 数列の要素数
M = int(first[1])  # 数列の最大値
Q = int(first[2])

inp = list()

for _ in range(Q):
    inp.append(sys.stdin.readline().strip())


max_score = 0
As = list()


def loop(row, start, idx):

    global max_score

    if idx == N:
        # As.append(row)
        score = 0
        for item in inp:
            a, b, c, d = map(int, item.split())
            if row[b - 1] - row[a - 1] == c:
                score += d
        max_score = max(score, max_score)

    else:
        for i in range(start, M+1):
            loop(row + [i], i, idx+1)


loop([], 1, 0)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import sys

first = sys.stdin.readline().strip().split()
N = int(first[0])  # 数列の要素数
M = int(first[1])  # 数列の最大値
Q = int(first[2])

inp = list()

for _ in range(Q):
    inp.append(sys.stdin.readline().strip())


max_score = 0
As = list()


def loop(row, start, idx):

    if idx == N:
        As.append(row)
    else:
        for i in range(start, M+1):
            loop(row + [i], i, idx+1)


loop([], 1, 0)

for A in As:
    score = 0
    for item in inp:
        a, b, c, d = map(int, item.split())
        if A[b-1] - A[a-1] == c:
            score += d
    max_score = max(score, max_score)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
A=[0 for _ in range(N)]
query=[]
for _ in range(Q):
    query.append(tuple(map(int,input().split())))
list=[]
def dfs(v):
    for i in range(int(v[-1]),M):
        nv=v+str(i)
        if len(nv)==N+1:
            list.append(nv)
        else:
            dfs(nv)
dfs("0")
ans=0
for a in list:
    t_ans=0
    for q in query:
        if int(a[q[1]])-int(a[q[0]])==q[2]:
            t_ans+=q[3]
    ans=max(ans,t_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, Q = [int(i) for i in input().split()]
pos_A = sorted([i for i in range(1, M+1)] * N)
comb_A = list(itertools.combinations(pos_A, N))
score = [0 for _ in comb_A]
for i in range(Q):
    a, b, c, d  = [int(i) for i in input().split()]
    for j, k in enumerate(comb_A):
        if k[b-1] - k[a-1] == c:
            score[j] += d
print(max(score))

Submission status: Time Limit Exceeded

Solution code:
import copy


def get_pattern(idx, length, num, pattern):
    if num == 0:
        yield pattern
        return

    if length < idx:
        return

    tmp = copy.deepcopy(pattern)
    for i in get_pattern(idx+1, length, num, tmp):
        yield i

    tmp = copy.deepcopy(pattern)
    tmp.append(idx)

    for i in get_pattern(idx, length, num-1, tmp):
        yield i


def get_conbination(num, M):
    pattern = []
    patterns = []
    for i in get_pattern(1, M, num, pattern):
        patterns.append(i)
    return patterns


N, M, Q = list(map(int, input().split()))
dic = {}

for _ in range(Q):
    a, b, c, d =\
        list(map(int, input().split()))
    dic[(a, b, c)] = d


patterns = get_conbination(N, M)

values = []

for pattern in patterns:
    value = 0
    for k, v in dic.items():
        if pattern[k[1]-1] - pattern[k[0]-1] == k[2]:
            value += v
    values.append(value)

print(max(values))

Submission status: Time Limit Exceeded

Solution code:
import copy


def get_pattern(idx, length, num, pattern, list1):
    if num == 0:
        yield pattern
        return

    if length < idx:
        return

    tmp = copy.deepcopy(pattern)
    for i in get_pattern(idx+1, length, num, tmp, list1):
        yield i

    tmp = copy.deepcopy(pattern)
    tmp.append(list1[idx])

    for i in get_pattern(idx, length, num-1, tmp, list1):
        yield i


def get_conbination(num, list1):
    pattern = []
    patterns = []
    for i in get_pattern(0, len(list1)-1, num, pattern, list1):
        patterns.append(i)
    return patterns


N, M, Q = list(map(int, input().split()))
dic = {}

for _ in range(Q):
    a, b, c, d =\
        list(map(int, input().split()))
    dic[(a, b, c)] = d

list1 = [0] * M
for i in range(1, M+1):
    list1[i-1] = i

patterns = get_conbination(N, list1)

values = []
for pattern in patterns:
    value = 0
    for k, v in dic.items():
        if pattern[k[1]-1] - pattern[k[0]-1] == k[2]:
            value += v
    values.append(value)
print(max(values))

Submission status: Time Limit Exceeded

Solution code:
import copy


def get_pattern(idx, length, num, pattern, list1):
    if num == 0:
        yield pattern
        return

    if length < idx:
        return

    tmp = copy.deepcopy(pattern)
    for i in get_pattern(idx+1, length, num, tmp, list1):
        yield i

    tmp = copy.deepcopy(pattern)
    tmp.append(list1[idx])

    for i in get_pattern(idx, length, num-1, tmp, list1):
        yield i


def get_conbination(num, list1):
    pattern = []
    patterns = []
    for i in get_pattern(0, len(list1)-1, num, pattern, list1):
        patterns.append(i)
    return patterns


N, M, Q = list(map(int, input().split()))
dic = {}

for _ in range(Q):
    a, b, c, d =\
        list(map(int, input().split()))
    if (a, b, c) in dic.keys():
        dic[(a, b, c)] += d
    else:
        dic[(a, b, c)] = d

list1 = []
for i in range(1, M+1):
    list1.append(i)

patterns = get_conbination(N, list1)

values = []
for pattern in patterns:
    value = 0
    for k, v in dic.items():
        if pattern[k[1]-1] - pattern[k[0]-1] == k[2]:
            value += v
    values.append(value)
print(max(values))

Submission status: Time Limit Exceeded

Solution code:
import itertools
A = list(map(int,input().split()))
N, M, Q = A[0], A[1], A[2]
B = [list(map(int,input().split())) for _ in range(Q)]

M_list = [i for i in range(1, M+1)]
c = itertools.combinations_with_replacement(M_list, N)
max_list = []
for N_list in c:
    #print(N_list)
    d_list = []
    for i in range(Q):
        a = B[i][0]
        b = B[i][1]
        c = B[i][2]
        d = B[i][3]

        if N_list[b-1] - N_list[a-1] == c:
            d_list.append(d)
        else:
            d_list.append(0)
    max_list.append(sum(d_list))
print(max(max_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

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

max_value = 0
#for A in itertools.permutations(range(1, M+1), N):
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp_value = 0
    for i in range(len(S)):
        if S[i][1] > len(A) or S[i][0] > len(A):
            continue

        if A[S[i][1] - 1] - A[S[i][0] - 1] == S[i][2]:
            tmp_value += S[i][3]
#            print(A, A[S[i][1] - 1], A[S[i][0] - 1], S[i][2], S[i])
    if tmp_value > max_value:
        max_value = tmp_value
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import math
import copy

def minx(idx, cl, m):
    mi = 1
    for i in range(idx):
        mi = max(mi, cl[i])
    return mi

def maxx(idx, cl, m):
    ma = m
    for i in range(idx + 1, len(cl)):
        if cl[i] > 0 and cl[i] < ma:
            ma = cl[i]
    return ma

def maxp(qs, idx, cl, n, m, cache):
    k = str(idx) + ':' + ':'.join(map(str, cl))
    if k in cache:
        return cache[k]

    (a, b, c, d) = qs[idx]

    if idx == len(qs) - 1:
        mp = 0
        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    mp = d
                    break
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)
                if mia <= na <= maa:
                    mp = d
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                

                if mib <= nb <= mab:
                    mp = d

        elif cl[b - 1] - cl[a - 1] == c:
            mp = d

        cache[k] = mp
    else:
        #not select
        mp = maxp(qs, idx + 1, cl, n, m, cache)

        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)                
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        else:
            if cl[b - 1] - cl[a - 1] == c:
                mp = max(mp, d + maxp(qs, idx + 1, cl, n, m, cache))
                
        cache[k] = mp

    return cache[k]

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

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

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 0, l, n, m, cache))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

arrays = []
n,m,q = 0,0,0

def main():
    global n, m, q
    global arrays
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    dfs([], 1)
    for array in arrays:
        tmp = 0
        for i in range(q):
            if array[abcd[i][1]-1] - array[abcd[i][0]-1] == abcd[i][2]:
                tmp += abcd[i][3]
        ans = max(ans, tmp)
    print(ans)

def dfs(stack, i):
    stack.append(i)
    if len(stack) == n:
        arrays.append(copy.deepcopy(stack))
        if i < m:
            stack.pop()
            dfs(copy.deepcopy(stack), i + 1)
        return
    dfs(copy.deepcopy(stack), i)
    if i < m:
        stack.pop()
        dfs(copy.deepcopy(stack), i + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

Submission status: Time Limit Exceeded

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

#左側にあるボールの数 + 1
A = [1]*(M-1)
B = [0]*N
lis = A + B
max_result = 0

import itertools
 
permutations_lis = itertools.permutations(lis)
#全ての場合のリスト

for one_case in permutations_lis:
  A = [0]*N
  q = 1
  i = 0
  for j in one_case:
    if j == 0:
      A[i] = q
      i += 1
    else:
      q += 1
    #点数の計算
    count = 0
    for k in range(Q):
      a,b,c,d = data[k][0],data[k][1],data[k][2],data[k][3]
      if A[b-1]-A[a-1] == c:
        count += d
    max_result = max(count,max_result)
    
print(max_result)

Submission status: Time Limit Exceeded

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

# C - Many Requirements
import copy

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

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

for i in range(n):
	tmp_arr = []
	
	for s in seq_arr:
		for j in range(s[-1], m + 1):
			tmp_arr.append(s + [j])

	seq_arr = copy.deepcopy(tmp_arr)

queries = []

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

ans = 0

for seq in seq_arr:
	sum = 0
	
	for query in queries:
		a, b, c, d = query
		
		if seq[b] - seq[a] == c:
			sum += d
			
	ans = max(ans, sum)

print(ans)

Submission status: Time Limit Exceeded

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

def DFS(s):
    if len(s) == N:
        return [s]
    ans = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        ans.extend(DFS(s+str(i)))
    return ans


V = DFS('')
final_ans = 0
for v in V:
    answer = 0
    A = [int(c)+1 for c in v]
    for a, b, c, d in abcd:
        if int(v[b-1]) - int(v[a-1]) == c:
            answer += d
    final_ans = max(final_ans , answer)
print(final_ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
M_chr = []
for i in range(1,M+1):
    M_chr.append(str(i))
As = list(itertools.combinations_with_replacement(M_chr, N))
pointA_max = 0
for i, A in enumerate(As):
    pointA = 0
    for i in range(Q):
        a = abcd[i][0]
        b = abcd[i][1]
        c = abcd[i][2]
        d = abcd[i][3]
        if int(A[b-1])-int(A[a-1]) == c:
            pointA = pointA + d
    if pointA_max < pointA:
        pointA_max = pointA
print(pointA_max)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
M_chr = []
for i in range(1,M+1):
    M_chr.append(str(i))
As = list(itertools.combinations_with_replacement(M_chr, N))
pointA_max = 0
for i, A in enumerate(As):
    pointA = 0
    for i in range(Q):
        a = abcd[i][0]
        b = abcd[i][1]
        c = abcd[i][2]
        d = abcd[i][3]
        if int(A[b-1])-int(A[a-1]) == c:
            pointA = pointA + d
    if pointA_max < pointA:
        pointA_max = pointA
print(pointA_max)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N, M, Q = map(int, readline().split())
A = np.array(list(itertools.combinations_with_replacement(range(1, M+1), N)))

n = len(A) 

score = np.zeros(n, np.int32)
m = np.array(read().split(), np.int32).reshape(Q, 4)

ans = 0
for com in A:
    tmp = 0
    for a, b, c, d in m: 
        if com[b-1]-com[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:



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

ans = 0

def check(lst):
    global ans
    tmp = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] == lst[a-1] + c:
            tmp += d
    ans = max(ans, tmp)

def solve(idx, lst):

    if idx >= N:
        check(lst)
        return
    
    if idx <= 0:
        lo = 1
    else:
        lo = lst[idx-1]

    for i in range(lo, M+1):
        
        lst[idx] = i
        solve(idx+1, lst)


lst = [0] * N
for i in range(1, M+1):
    solve(0, lst)
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
m = list()
res = -100
for i in range(Q):
    n = list(map(int, input().split()))
    m.append(n)
l = [x for x in range(1, M + 1)]
p = itertools.combinations_with_replacement(l, N)
for p in p:
    total = 0
    for i in range(Q):
        num = 0
        a = m[i][0]
        b = m[i][1]
        A = p[a - 1]
        B = p[b - 1]
        C = B - A
        if m[i][2] == C:
            num = num + m[i][3]
            total = total + num
    if res < total:
        res = total
print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
m = list()
res = -100
for i in range(Q):
    n = list(map(int, input().split()))
    m.append(n)
l = list()
for i in range(M):
    l.append(i + 1)
p = itertools.combinations_with_replacement(l, N)
for p in p:
    total = 0
    for i in range(Q):
        num = 0
        a = m[i][0]
        b = m[i][1]
        A = p[a - 1]
        B = p[b - 1]
        C = B - A
        if m[i][2] == C:
            num = num + m[i][3]
            total = total + num
    if res < total:
        res = total
print(res)

Submission status: Time Limit Exceeded

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

def DFS(s):
    if len(s) == N:
        return [s]
    ans = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        ans.extend(DFS(s+str(i)))
    return ans


V = DFS('')
final_ans = []
for v in V:
    answer = 0
    for q in abcd:
        if int(v[q[1]-1]) - int(v[q[0]-1]) == q[2]:
            answer += q[3]
    final_ans.append(answer)
print(max(final_ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

def f(data, q, cnd):
    res = 0
    for i in range(q):
        a, b, c, d = data[i]
        if int(cnd[b])-int(cnd[a]) == c:     
            res += d
    return res

def main():
    n, m, q = map(int, readline().split())
    data = []
    for _ in range(q):
        a, b, c, d = map(int, readline().split())
        a-=1
        b-=1
        data.append((a, b, c, d))  
    
    cnd = []
    dq = deque() 
    for i in range(1, m+1):
        dq.append(i)
    while len(dq)>0:
        v = dq.popleft() 
        u = v%10 
        for i in range(u, m+1):
            nx = v*10+i
            if len(str(nx)) == n:
                cnd.append(str(nx))
            else:
                dq.append(nx)
    ans = 0
    for i in cnd:
        ans = max(ans, f(data, q, i))
    print(ans) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
def dfs(i,A):
    #print(A)
    global ans 
    tmp = 0
    for a,b,c,d in li:
        if (A[b-1] - A[a-1]) == c:
            tmp += d
    ans = max(ans,tmp)
    if i == m:
        return
    for j in range(n):
        A_tmp = A[:]
        for k in range(1,j+2):
            A_tmp[-k] += 1
        dfs(i+1,A_tmp)
dfs(1,[1]*n)
print(ans)

Submission status: Time Limit Exceeded

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())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        for k in range(j,M+1):
          dfs(k,M,N,tmp)
    
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Submission status: Time Limit Exceeded

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())

ans_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    if len(ans)==N:
      if ans not in ans_list:
        ans_list.append(ans)
    else:
      for i in range(x,M+1):
        tmp=deepcopy(ans)
        dfs(i,M,N,tmp)   
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement

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_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    for i in range(x,M+1):
      tmp=deepcopy(ans)
      dfs(i,M,N,tmp)
  else:    
    if ans not in ans_list:
      ans_list.append(ans)
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
lch = len(ch)
rel = [0]*lch
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(lch):
    for i in range(q):
        a = l[i][0]
        b = l[i][1]
        c = l[i][2]
        d = l[i][3]
        if ch[k][b-1]-ch[k][a-1]==c:
            rel[k]+=d
print(max(rel))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q = map(int,input().split())
ch = list(itertools.combinations_with_replacement(range(1,m+1),n))
rel = [0]*len(ch)
l = [list(map(int,input().split())) for _ in range(q)]
for k in range(len(ch)):
    for i in range(q):
        a = l[i][0]
        b = l[i][1]
        c = l[i][2]
        d = l[i][3]
        if ch[k][b-1]-ch[k][a-1]==c:
            rel[k]+=d
print(max(rel))

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n=0
m=0
ans=-inf
l=[]

def dfs(s):
  global n
  global m
  global ans
  global l

  if len(s)==n:
    _ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if int(s[b])-int(s[a])==c:
        _ans+=d
    ans=max(ans,_ans)

  if len(s)!=n:
    x=int(s[-1])
    for i in range(x,m+1):
      dfs(s+str(i))

def main():
  global n
  global m
  global ans
  global l

  n,m,q=LI()
  l=[LI() for _ in range(q)]

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

  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    ai, bi, ci, di = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

h = []
A_list = np.array(list(itertools.combinations_with_replacement(range(1, m+1), n)))


for A in A_list:
    s = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    h.append(s)

print(max(h))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    ai, bi, ci, di = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

h = 0
it = itertools.combinations_with_replacement(range(1, m+1), n)
A_list = np.array(list(it))


for A in A_list:
    s = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    h = max(h, s)

print(h)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

a=[]
b=[]
c=[]
d=[]

for i in range(q):
    ai, bi, ci, di = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)
    c.append(ci)
    d.append(di)

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

h = 0
it = itertools.combinations_with_replacement(range(1, m+1), n)
A_list = np.array(list(it))


for A in A_list:
    h = max(h, score(A,a,b,c,d))

print(h)

Submission status: Time Limit Exceeded

Solution code:
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

N, M, Q = map(int,input().split())
S = [[int(x) for x in input().split()]for i in range(Q)]
Max = 0
for i in range((M+1)**(N-1),(M+1)**N):
  count = 0
  a = Base_10_to_n(i, M+1)
  if a.count('0') != 0:
    continue
  else:
    A = [int(k) for k in list(a)]
    A.sort()
    for j in range(Q):
      if A[S[j][1]-1]-A[S[j][0]-1] == S[j][2]:
        count += S[j][3]
    if count > Max:
      Max = count
print(Max)

Submission status: Time Limit Exceeded

Solution code:
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

N, M, Q = map(int,input().split())
S = [[int(x) for x in input().split()]for i in range(Q)]
Max = 0
for i in range((M+1)**(N-1),(M+1)**N):
  count = 0
  if Base_10_to_n(i, M+1).count('0') != 0:
    continue
  else:
    A = [int(k) for k in list(Base_10_to_n(i, M+1))]
    A.sort()
    for j in range(Q):
      if A[S[j][1]-1]-A[S[j][0]-1] == S[j][2]:
        count += S[j][3]
    if count > Max:
      Max = count
print(Max)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(q)]
m -= 1
As = []


def gen_A(x, y, A, c):
  global As
  if x == n and y == m:
    As.append(A)
    return
  if x < n:
    nA = A+str(c)
    gen_A(x+1, y, nA, c)
  if y < m:
    nc = c+1
    gen_A(x, y+1, A, nc)


gen_A(0, 0, "", 0)
mx = 0
for A in As:
  pts = 0
  for i in l:
    if int(A[i[1]-1])-int(A[i[0]-1]) == i[2]:
      pts += i[3]
  mx = max(mx, pts)
print(mx)

Submission status: Time Limit Exceeded

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

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

def bit_iter(x):
    while x:
        yield x & 1
        x >>= 1


scores = []
for state in range(1 << q):
    A = [None] * n
    score = 0
    for i, v in enumerate(bit_iter(state)):
        if v:
            a, b, c, d = query[i]
            if A[a] is None:
                if A[b] is None:
                    A[a] = 1
                else:
                    A[a] = A[b] - c

            if A[a] and A[b] and A[b] - A[a] != c:
                break

            A[b] = c + A[a]
            if A[a] < 1 or A[b] > m:
                break
            score += d
    else:
        scores.append(score)
print(max(scores))

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
    
import itertools
scorelist=[]
k = itertools.product(range(1,M+1), repeat=N)
for i in k:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    scorelist.append(score)
print(max(scorelist))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(itertools.product(range(1,M+1), repeat=N))
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = list(map(int,input().split()));

data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));

A = [1]*n;
ans = 0;
As = [A];

for i in As :
    A_now = As.pop(-1);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;


print(ans);