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:
def create_new(l, m):
    i = 0
    while(1):
        if l[i] == m:
            l[i] = 0
            i += 1
        else:
            l[i] += 1
            break
    return l


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

l = []

A = [1]*N



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

l.sort(key=lambda tup: tup[3])


mscore = 0
for _ in range(M**N):
    score = 0
    for tup in l:
        if A[N-tup[1]]-A[N-tup[0]] == tup[2]:
            score += tup[3]
    mscore = max(mscore, score)
    create_new(A, M)

print(mscore)

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import defaultdict


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

    m_list = defaultdict(list)

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

    for data in abcd:
        for i in range(1, m+1):
            for j in range(i+1, m+1):
                if j - i == data[2]:
                    if m_list[data[0]][0] == 0:
                        m_list[data[0]] = [i]
                    else:
                        m_list[data[0]].append(i)
                    if m_list[data[1]][0] == 0:
                        m_list[data[1]] = [j]
                    else:
                        m_list[data[1]].append(j)

    ll = list(product(*m_list.values()))

    ans = 0
    for l in ll:
        tmp = 0
        for data in abcd:
            if l[data[1]-1] - l[data[0]-1] == data[2]:
                tmp += data[3]
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

s_list = []
N, M, Q = map(int, input().split())  # 1行目のNを取得する
A_list = []
num = 1
while num <= Q:
    num += 1
    a, b, c, d, = map(int, input().split())  # 複数行の数値の入力を取得
    s_list.append(list([a, b, c, d]))  # a,b,c,dを作る
for i in range(1, M+1, 1):
    A_list.append(i)

hairetsu_list = []  # Aだよ
for v in itertools.permutations(A_list, N):
    hairetsu_list.append(v)
    
score_list = []
for hairetsu in hairetsu_list:
    score = []
    for s in s_list:
        if hairetsu[s[1]-1] - hairetsu[s[0]-1] == s[2]:
            # print(hairetsu,s[3])
            score.append(s[3])
    score_list.append(sum(score))
print(max(score_list))

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
a=list()
b=list()
c=list()
d=list()
Ax=list()
dx=list()
p=0
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)
    

for i in range(M):
    for j in range(i,M):
        for k in range(j,M):
            Ax.append([i+1,j+1,k+1])
            p+=1
for j in range(p):
    Dx=0
    for i in range(Q):
        
        if Ax[j][b[i]-1]-Ax[j][a[i]-1]==c[i]:
            Dx=Dx+d[i]
    dx.append(Dx)


print(max(dx))

Submission status: Runtime Error

Solution code:
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 
    n,m,q = map(int,input().strip().split())
    abcd = []
    for i in range(q):
        # a,bはindexの次元，cは値， dはポイント
        temp_a,temp_b,temp_c,temp_d = map(int,input().strip().split())
        abcd.append((temp_a - 1, temp_b - 1, temp_c, temp_d ))

    # 
    eprint('n,m,q ',end=':\n')
    eprint(n,m,q)
    eprint('abcd ',end=':\n')
    eprint(abcd)

    #
    ans=0
    # l=[i for i in range(1,m+1)]
    # ll=[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]
    for p in range(1,m+1):
        for j in range(p,m+1):
            for k in range(j,m+1):
                for l in range(k,m+1):
                    A=[p,j,k,l]
                    point = 0
                    for i in range(q):
                        a=abcd[i][0]
                        b=abcd[i][1]
                        c=abcd[i][2]
                        d=abcd[i][3]
                        if A[b] - A[a] == c:
                            point+=d
                    ans = max(point,ans)
    print(ans)   
    # for A in itertools.combinations(ll,n):
    #     #
    #     eprint('A ',end=':\n')
    #     eprint(A)

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

if __name__ == '__main__':
    main()

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()
A = [1] * N
while A != [M] * N:
  for i in range(Q-1):
    ai = P[i][0] - 1
    bi = P[i][1] - 1
    ci = P[i][2]
    if A[bi] - A[bi] == ci:
      score += P[i][3]
    scores.append(score)
print(max(scores))

Submission status: Runtime Error

Solution code:
# coding: utf-8

N, M, Q = map(int,input().split())
L = []
A = [1] * N
ans = 0

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

L.sort(key=lambda x:x[3])

for i in range(Q):
    a=L[i][0]
    b=L[i][1]
    c=L[i][2]
    d=L[i][3]
    if A[b-1] <= A[a-1] + c <= M:
        ans += d
        #print(ans)
        A[b-1:] = [A[a-1] + c] * (N-A[a-1]+c-1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import math

N, M, Q = (int(x) for x in input().split())
S = np.array([list(map(int,input().split(" "))) for i in range(Q)])
print(S)
sum = np.zeros(M)
a = 0

for i in range(M):
    for j in range(Q):
        if S[j,2] == i:
            s = a if a > S[j:3] else S[j:3]
        sum[i] = a

print(math.floor(np.sum(sum)))

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

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

A = []
tmp = []
for i in range(1, m+1):
    for j in range(i, m+1):
        for k in range(j, m+1):
            A.append([i, j, k])

cnt = 0

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

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
p = [input().split() for i in range(q)]
#和がm-1以下となるn個のリストを列挙する
global samples
samples= []
def rekkyo(M, N, lists,maxlen):
    if N>0:
        for i in range(M):
            lists.append(i)
            if len(lists) == maxlen:
                samples.append(copy.copy(lists))
            else:
                rekkyo(M-i,N-1,lists,maxlen)
            lists.pop(-1)

rekkyo(m,n,[],n)
ans = 0
for i in samples:
    tmp=0
    for j in p:
        if sum(i[int(j[0]):int(j[1])]) == int(j[2]):
            tmp+=int(j[3])
    if ans<tmp:
        ans=tmp

print(ans)

Submission status: Runtime Error

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

A = list(itertools.combinations(range(1,M+1), 3))
number = len(A)

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

Submission status: Runtime Error

Solution code:
import copy

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

rules = list()

for _ in range(q):
    a, b, c, d = list(map(int, input().split()))
    rules.append((a, b, c, d))

rules = sorted(rules, key=lambda x: x[1])

answers = [[-1 if i > 1 else 1 for i in range(n + 1)]]
answers[0][0] = 0
for r in rules:
    a, b, c, d = r
    new_answers = list()
    for ans in answers:
        if ans[b] == -1 or ans[b] == ans[a] + c:
            if ans[a] + c <= m:
                new_answer = copy.copy(ans)
                new_answer[0] = ans[0] + d
                new_answer[b] = ans[a] + c

                new_answers.append(new_answer)
    answers.extend(new_answers)

print(max([ans[0] for and in answers]))
exit()


As = [[-1 for i in range(m + 1)] for j in range(n + 1)]

As[1][1] = 0

for r in rules:
    a, b, c, d = r
    for i in range(1, m + 1):
        if i + c <= m:
            if As[a][i] < 0:
                continue
            if As[b][i+c] >= 0:
                As[b][i + c] += As[a][i] + d
            else:
                As[b][i + c] = As[a][i] + d

    print(As)

Submission status: Runtime Error

Solution code:
from itertools import *
from more_itertools import *

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

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

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

a=list(combinations_with_replacement(aaa,n))
ans=0
for i in a:
    aa=0
    for j in l:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            aa+=j[3]
    if aa>ans:
        ans=aa
print(ans)

Submission status: Runtime Error

Solution code:
def count_up(x,n):
  x[n]+=1
  if x[n]>m:
    count_up(x,n-1)
    x[n]=x[n-1]
  return
n,m,q=map(int,input().split())
abcd=[map(int,input().split()) for _ in range(q)]
a,b,c,d=[list(i) for i in zip(*abcd)]
x=[1,1,1,1,1,1,1,1,1,1,1]
ans=0
while x[1]==1:
  temp=0
  for i in range(q):
    if x[b[i]]-x[a[i]]==c[i]:
      temp+=d[i]
  ans=max(ans,temp)
  count_up(x,n)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N,M,Q=map(int,input().split())
ABC=[]
ans=0
take=set([])
for i in range(Q):
  ABC+=[list(map(int,input().split()))]
ABC.sort(key=lambda x: x[3],reverse=True)
for i in range(N):
  if len(take)==N:
    print(ans)
    sys.exit
  ans+=ABC[i][3]
  take.add(ABC[i][0])
  take.add(ABC[i][1])
  take=set(take)

Submission status: Runtime Error

Solution code:


from itertools import permutations, combinations, combinations_with_replacement, product


def main():
    a = list(map(int, input().split()))
    N = a[0]
    M = a[1]
    Q = a[2]
    b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    b = b[0:M]

    comb = list(combinations(b, M-1))
    size = len(comb)
    maxscore = 0
    Z = []
    for j in range(1, Q+1, 1):
        Z.append(list(map(int, input().split())))

    for i in range(0, size, 1):
        score = 0
        for j in range(0, Q, 1):
            ai = Z[j][0] - 1
            bi = Z[j][1] - 1
            ci = Z[j][2]
            di = Z[j][3]
            combi = comb[i]
            if ci == combi[bi] - combi[ai]:
                score = score + di
        if maxscore < score:
            maxscore = score
    print(maxscore)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

a = [list(map(int, input().split())) for i in range(q)]
seq=[]
for j in range(1,m+1):
  sea=[j]*(n//2)
  seq=seq+sea
ddd=list(itertools.combinations(seq, n))
y=0
ppp=[]
for c in ddd:
  for b in a:
    if c[b[1]-1]-c[b[0]-1]==b[2]:
      y+=b[3]
  ppp.append(y)
  y=0
p2=sorted(ppp)
print(p2[-1])

Submission status: Runtime Error

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

def main():
  n,m,q=LI()
  l=[False]*n
  ans=0

  ll=[]
  for _ in range(q):
    _l=LI()
    ll.append(_l)

  for i in range(1<<n):
    l=[False]*n
    _ans=0
    for j in range(n):
      if i&(1<<j):
        a,b,c,d=ll[j]
        a-=1
        b-=1
        if l[a] and l[b]:
          continue
        l[a]=True
        l[b]=True
        _ans+=d
    ans=max(ans,_ans)
  return ans

# main()
print(main())

Submission status: Runtime Error

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

dd = sorted(d,reverse = True)[:2]
print(sum(dd))

Submission status: Runtime Error

Solution code:
import itertools
n,m,q=map(int,input().split())
lis=[i for i  in range(1,m+1)]
lis=list(itertools.combinations(lis,n))
box=[0 for j in range(len(lis))]
que=[list(map(int,input().split())) for k in range(q)]
for i in range(q):
    for j in range(len(lis)):
        if lis[j][que[i][1]-1]-lis[j][que[i][0]-1]==que[i][2]:
            box[j]+=que[i][3] 
print(max(box))

Submission status: Runtime Error

Solution code:
import itertools

n, m, q = [int(x) for x in input().split()]
 
tmp = []
for i in range(q):
    a, b, c, d = [int(x) for x in input().split()]
    tmp.append([a, b, c, d])

t = list(itertools.combinations_with_replacement(range(1, m + 1), m-1))

score = 0
for _t in t:
    _s = 0
    for a, b, c, d in tmp:
        if c == _t[b - 1] - _t[a - 1]:
            _s += d
    score = max(_s, score)
print(score)

Submission status: Runtime Error

Solution code:
n,m,q = map(int, input().split())
'''
arr = []
for i in range(1,n+1):
    if(i<=m):
        arr.append(i)
print(arr)
'''
arr = [1,n,m]
sm=0
while(q):
    a,b,c,d = map(int, input().split())
    if(arr[b-1]-arr[a-1]==c):
        sm+=d
    q-=1
print(sm)

Submission status: Runtime Error

Solution code:
import math
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())

maximum = 0
lis = list(range(1, M+1, 1))
for pair in itertools.combinations(lis, N):
    sum = 0
    pair = list(pair)
    for i in range(N):
        if pair[b[i]-1]-pair[a[i]-1] == c[i]:
            sum += d[i]
            
    if maximum < sum:
        maximum = sum

print(maximum)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import copy
import sys
sys.setrecursionlimit(2*10**9)
def solve(n, m, q, A):
  if len(A) == m+1:
    rtn = 0
    for b, v in q.items():
      if v:
        for a, c, d in v:
          rtn += d if A[b]-A[a] == c else 0
    return rtn
  else:
    rtn = 0
    xs = []
    for i in range(A[-1], m+1):
      b = len(A)
      for a, c, _ in q[b]:
        if i-A[a] == c:
          xs.append(i)
    return max([solve(n, m, q, A+[x]) for x in (set(xs) if xs else range(A[-1], m+1))])

N, M, Q = map(int, input().split())
dic = {i:[] for i in range(1, M+1)}
for _ in range(Q):
  a, b, c, d = map(int, input().split())
  dic[b].append((a, c, d))
print(solve(N, M, dic, [1]))

Submission status: Runtime Error

Solution code:
n,m,q = map(int, input().split())
print(n,m,q)
'''
arr = []
for i in range(1,n+1):
    if(i<=m):
        arr.append(i)
print(arr)
'''
arr = [1,n,m]
sm=0
while(q):
    a,b,c,d = map(int, input().split())
    print(a,b,c,d)
    if(arr[b-1]-arr[a-1]==c):
        sm+=d
    q-=1
print(sm)

Submission status: Runtime Error

Solution code:
import itertools
n,m,q = map(int,input().split())
array = []
A = [i for i in range(1,m+1)]
A_list = list(itertools.combinations(A,n))
max_sum = [0]*len(A_list)

for i in range(q):
    a,b,c,d = map(int,input().split())
    for j in range(len(A_list)):
        if A_list[j][b-1]-A_list[j][a-1] == c:
            max_sum[j] += d
print(max(max_sum))

Submission status: Runtime Error

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

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

for i in range(N) :
    if A[res[i][1]] - A[res[i][0]] == res[i][2] :
        d += res[i][3]
print(d)

Submission status: Runtime Error

Solution code:
import itertools
n,m,q = map(int,input().split())
array = []
A = [i for i in range(1,m+1)]
A_list = list(itertools.combinations(A,n))
max_sum = [0]*len(A_list)

for i in range(q):
    a,b,c,d = map(int,input().split())
    for j in range(len(A_list)):
        if A_list[j][b-1]-A_list[j][a-1] == c:
            max_sum[j] += d
print(max(max_sum))

Submission status: Runtime Error

Solution code:
N,M,Q = map(int,input().split())
a=['']*Q
b=['']*Q
c=['']*Q
d=['']*Q
score = 0
if Q == 1:
    print(input().split()[3])
for i in range(Q):
    a,b,c,d=map(int,input().split())
    if c<=M-1 and c>=0:
        score = score + d

Submission status: Runtime Error

Solution code:
def main():
    n,m,q=map(int,input().split())
    ABCD=[list(map(int,input().split())) for _ in range(q)]
    ans=0
    L=list(range(1,m+1))
    for Q in combinations_with_replacement(L,n):
        Q=list(sorted(Q))
        tmp=0
        for a,b,c,d in ABCD:
            if Q[b-1]-Q[a-1]==c:
                tmp+=d
        ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
cmb = [map(int,input().split() for i in range(q)]
cmb = sorted(cmb)
ans = 0
box = [[-float("inf"),-float("inf")]*(n+1)]*(n+1)

for i in cmb:
    if box[i[0]][i[1]] == -float("inf"):
        for j in box[i[0][i[0]:i[1]]][0]:
            aaa = 0
            if j[0] > i[2]:
                aaa += j[1]
        if aaa < i[3]:
            box[i[0]][i[1]] = [i[2],i[3]]
            ans += i[3]
         


    else:
        if box[i[0]][i[1]][0]<i[3]:
            for j in box[i[0][i[0]:i[1]]][0]:
            aaa = 0
                if j[0] > i[2]:
                aaa += j[1]
            if aaa < i[3]:
                box[i[0]][i[1]] = i[2]
                ans += i[3]

print(ans)

Submission status: Runtime Error

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

A = itertools.combinations([q for q in range(1,(M+1))], N)
count=[]
for a in A:
    tmp=0
    for l in L:
        if a[l[1]-1] - a[l[0]-1] == l[2]:
            tmp+=l[3]
        else:
            pass
    count.append(tmp)

print(max(count))

Submission status: Runtime Error

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

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

import itertools
a=list(itertools.combinations(range(1,M+1),N))

import math
com=math.factorial(M)*math.factorial(M-N)//math.factorial(N)

ans=[0 for l in range(com)]

for k in range(Q):
    for j in range(com):
        if a[j][t[k][1]-1]-a[j][t[k][0]-1]==t[k][2]:
            ans[j]=t[k][3]+ans[j]
        else:
            pass
print(max(ans))

Submission status: Runtime Error

Solution code:
def main():
  n, m, q = map(int, input().split())
  table = []
  table.sort(key=lambda x: x[0])
  ls = []
  for i in range(q):
    table.append(list(map(int, input().split())))
  ans = 0
  for i in range(2**q):
    A = [-1 for _ in range(n+1)] 
    A[0] = 1
    tmp = 0
    for j in range(q):
      if ((i>>j)&1):
        if (A[table[i][1]-1] != -1) and (A[table[i][0]-1] != -1):
          if A[table[i][1]-1] - A[table[i][0]-1] != table[i][2]:
            break
        elif (A[table[i][1]] == -1):
          A[table[i][1]-1] = A[table[i][0]-1] + table[i][2]
      tmp += table[i][3]
    else:
      if ans < tmp:
        ans = tmp
  print(ans)
  
  
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N,M,Q = [int(x) for x in input().split()]
#全探索する
from collections import deque
nyu = []
for i in range(Q):
    nyu.append([int(x) for x in input().split()])
d = deque()
a = [0] * (N+1)
e = []
ima = 0
ans = 0
if N == 2:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2)
        for j in range(i,M+1):
            a[2] = j
            for i in range(Q):
                aa = nyu[i][0]
                bb = nyu[i][1]
                cc = nyu[i][2]
                dd = nyu[i][3]
                if a[bb] - a[aa] == cc:
                    ima += dd
            ans = max(ans,ima)
            ima = 0
elif N == 3:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for i in range(Q):
                    aa = nyu[i][0]
                    bb = nyu[i][1]
                    cc = nyu[i][2]
                    dd = nyu[i][3]
                    if a[bb] - a[aa] == cc:
                        ima += dd
                ans = max(ans,ima)
                ima = 0

elif N == 4:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for i in range(Q):
                        aa = nyu[i][0]
                        bb = nyu[i][1]
                        cc = nyu[i][2]
                        dd = nyu[i][3]
                        if a[bb] - a[aa] == cc:
                            ima += dd
                    ans = max(ans,ima)
                    ima = 0
elif N == 5:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for i in range(2):
                        sinigami = 2
                    for m in range(l,M+1):
                        a[5] = m
                        for i in range(Q):
                            aa = nyu[i][0]
                            bb = nyu[i][1]
                            cc = nyu[i][2]
                            dd = nyu[i][3]
                            if a[bb] - a[aa] == cc:
                                ima += dd
                        ans = max(ans,ima)
                        ima = 0
elif N == 6:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for i in range(Q):
                                aa = nyu[i][0]
                                bb = nyu[i][1]
                                cc = nyu[i][2]
                                dd = nyu[i][3]
                                if a[bb] - a[aa] == cc:
                                    ima += dd
                            ans = max(ans,ima)
                            ima = 0
elif N == 7:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for i in range(Q):
                                    aa = nyu[i][0]
                                    bb = nyu[i][1]
                                    cc = nyu[i][2]
                                    dd = nyu[i][3]
                                    if a[bb] - a[aa] == cc:
                                        ima += dd
                                ans = max(ans,ima)
                                ima = 0
elif N == 8:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for i in range(Q):
                                        aa = nyu[i][0]
                                        bb = nyu[i][1]
                                        cc = nyu[i][2]
                                        dd = nyu[i][3]
                                        if a[bb] - a[aa] == cc:
                                            ima += dd
                                    ans = max(ans,ima)
                                    ima = 0
elif N == 9:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for r in range(q,M+1):
                                        a[9] = r
                                        for i in range(Q):
                                            aa = nyu[i][0]
                                            bb = nyu[i][1]
                                            cc = nyu[i][2]
                                            dd = nyu[i][3]
                                            if a[bb] - a[aa] == cc:
                                                ima += dd
                                        ans = max(ans,ima)
                                        ima = 0
elif N == 10:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for r in range(q,M+1):
                                        a[9] = r
                                        for s in range(r,M+1):
                                            a[10] = s
                                            for i in range(Q):
                                                aa = nyu[i][0]
                                                bb = nyu[i][1]
                                                cc = nyu[i][2]
                                                dd = nyu[i][3]
                                                if a[bb] - a[aa] == cc:
                                                    ima += dd
                                            ans = max(ans,ima)
                                            ima = 0                                                                                  
print(ans)