Problem:


Score : 300 points

Problem Statement

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

Consider a sequence A satisfying the following conditions:

A is a sequence of N positive integers.

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

Let us define a score of this sequence as follows:

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

Find the maximum possible score of A.

Constraints

All values in input are integers.

2 ≤ N ≤ 10

1 \leq M \leq 10

1 \leq Q \leq 50

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum possible score of A.

Sample Input 1

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

Sample Output 1

110

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

Sample Input 2

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

Sample Output 2

357500

Sample Input 3

10 10 1
1 10 9 1

Sample Output 3

1



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


Sample output:
110

Submission status: Runtime Error

Solution code:
import itertools
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(tuple(map(int, input().split())))
    
c = itertools.combinations_with_replacement(list(range(1, M+1)), N)

m = 0
for i in c:
    flag = True
    sum = 0
    for j in l:
        if c[i[1]-1] - c[i[0]-1] == i[2]:
            sum += i[3]
    m = max(m, sum)
        
print(m)

Submission status: Runtime Error

Solution code:
import itertools

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

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

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

    # print(score_tmp)
    score_list.append(score_tmp)

print(max(score_list))

Submission status: Runtime Error

Solution code:
N,M,Q = map(int, input().split())
IN = [input().split() for i in range(N)]
import itertools
SC = []
score = 0

A = list(itertools.combinations(range(M), N))

for T in A:
    for i in IN:
        a = int(i[0])
        b = int(i[1])
        c = int(i[2])
        d = int(i[3])
        if  T[b] - T[a] == c:
            score += d
    SC.append(score)
    score = 0
print(SC)
print(max(SC))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement as cr
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(q)]
nl=[i for i in range(1,m+1)]
ansl=[]
for v in cr(nl,m):
  ans=0
  for a,b,c,d in l:
    if v[b-1]-v[a-1]==c:
      ans+=d
  ansl.append(ans)
print(max(ansl))

Submission status: Runtime Error

Solution code:
def check(a):
  for ind, val in enumerate(a):
    if(ind == len(a) - 1):
      return True
    if a[ind+1] < a[ind]:
      return False
    
  return True

def return_perm(n,m):
  ls = list(  map(list, permutations(range(1,m+1) , n)))

  return ls

n,m,qu = list(map(int, input().split()))
ls = return_perm(n,m)
ls = list(filter(check, ls))
max_sum = -1
for i in ls:
  sum = 0

  for j in range(qu):

    [a,b,c,d] = list(map(int, input.split()))

    if i[b] - i[a] == c:
      sum += d
    

  
  max_sum = max(max_sum, sum)


  print(max_sum)

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)[:m-1]
print(sum(dd))

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
S=[0]*Q;t=0;d=0;A=[0]*10
for i in range(Q):
  a,b,c,d=map(int,input().split())
  S[i]=[a,b,c,d]
#print(S)
for i1 in range(M):
  for i2 in range(M):
    for i3 in range(M):
      for i4 in range(M):
        for i5 in range(M):
          for i6 in range(M):
            for i7 in range(M):
              for i8 in range(M):
                for i9 in range(M):
                  for i10 in range(M):
                    A=[i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for i in range(Q):
                      if A[S[i][1]]-A[S[i][0]]==S[i][2]:
                        d=d+S[i][3]
                    t=max(t,d)
                    d=0
print(t)

Submission status: Runtime Error

Solution code:
import itertools
n,m,q=map(int,input().split())
qs = [list(map(int,input().split())) for i in range(q)]
mids = [i for i in range(m)]
# print(nums)
max_ans= 0
for mid in itertools.combinations_with_replacement(nums, n-1):
    if sum(mid)>m-1:
        continue
    sum_ans=0
    for i in qs:
        sum_mid = 0
        for j in range(i[0]-1,i[1]-1):
            sum_mid += mid[j]
        if sum_mid == i[2]:
            sum_ans += i[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
a = [0 for i in range(q)]
for i in range(q):
    a[i] = list(map(int,input().split()))
for i in range(1,m+1):
    for j in range(i,m+1):
        for k in range(j,m+1):
            for s in range(k,m+1):
                for p in range(s,m+1):
                    for l in range(p,m+1):
                        for e in range(l,m+1):
                            for u in range(e,m+1):
                                for v in range(u,m+1):
                                    b = [1,f,c,k,s,p,l,e,u,v]
                                    nn = 0
                                    for h in range(q):
                                        if b[a[h][1]-1] - b[a[h][0]-1] == a[h][2]:
                                            nn += a[h][3]
                                    ans = max(ans,nn)
print(ans)

Submission status: Runtime Error

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

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

point_list = []
for A in itertools.permutations(num_lis,N):
    A = sorted(list(A))
    point = 0
    for abcd in abcd_list:
        if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    point_list.append(point)

print(max(point_list))

Submission status: Runtime Error

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

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

from itertools import permutations, combinations,combinations_with_replacement,product
AA=range(1,M+1)
CM = list(combinations(AA,N))


wa =0
A=[0]*N
dammy=[]
for i in range(len(CM)):
        A = sorted(CM[i])
        for j in range(Q):
            #print(abcd[2][j])
            if (A[abcd[j][1]-1] - A[abcd[j][0]-1]) == abcd[j][2]:
                wa+=abcd[j][3]
        dammy.append(wa)
        wa =0

print(max(dammy))

Submission status: Runtime Error

Solution code:
import itertools

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

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([1, 0], repeat=q):
    cnt = 0
    aaa = []
    aaaa = set()
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
            cnt += d
    if ans < cnt:
        for a, b, c in aaa:
            for aa, bb, cc in aaa:
                if aa == a and b < bb:
                    aaaa.add([b, bb, cc - c])
                elif aa == a and b > bb:
                    aaaa.add([bb, b, c - cc])
                if b == bb and aa > a:
                    aaaa.add([a, aa, cc - c])
                elif b == bb and aa < a:
                    aaaa.add([aa, a, c - cc])
        aaa += list(aaaa)
        flag = True
        for i, (a, b, c, d) in enumerate(abcd):
            if bit[i] == 1:
                for aa, bb, cc in aaa:
                    if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                        if aa == a and bb == b and c == cc:
                            continue
                        else:
                            flag = False
                            break
                if not flag:
                    cnt = 0
                    break
        if ans < cnt:
            ans = cnt
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), N))
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:
[N,M,Q] = list(map(int,input().split()))

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

from itertools import permutations, combinations,combinations_with_replacement,product
AA=range(1,M+1)
CM = list(combinations(AA,N))


wa =0
A=[0]*N
dammy=[]
for i in range(len(CM)):
        A = sorted(CM[i])
        for j in range(Q):
            #print(abcd[2][j])
            if (A[abcd[j][1]-1] - A[abcd[j][0]-1]) == abcd[j][2]:
                wa+=abcd[j][3]
        dammy.append(wa)
        wa =0

print(max(dammy))

Submission status: Runtime Error

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

#sort by score
#[[score, index]...]
scLs = []
for ele in enumerate(ls):
    scLs.append([ele[1][3],ele[0] ])
scLs.sort(reverse=True)



selL = [2]*n
ans = -999

while True:
    buf = 0

    for ele in scLs:
        index = ele[1]
        a_index = ls[index][0]-1
        b_index = ls[index][1]-1
        c = ls[index][2]
        score = ls[index][3]

        if selL[a_index] - selL[b_index] == c:
            buf += score
        else:
            if ans < buf:
                ans = buf

    if selL[3] != "9":
        selL[3] = selL[3]+1
    elif selL[2] == "9":
        selL[3] = 0
        if selL[1] == "9":
            selL[2] = 0
            if selL[0] == "9":
                print(ans)
                sys.exit()
            else:
                selL[1] = 0
                selL[0] = selL[0]+1
        else:
            selL[2] = 0
            selL[1] = selL[1]+1
    else:
        selL[3] = 0
        selL[2] = selL[2]+1

Submission status: Runtime Error

Solution code:
import itertools
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
s=0
o=0
for i in range(Q):
    u,v,x,y=map(int,input().split())
    a.append(u)
    b.append(v)
    c.append(x)
    d.append(y)
for k in range(M):
    l=list(itertools.combinations(range(k+N), N))
    for x in l:
        s=0
        h=[]
        for i in range(N):
            h.append(x[i]-i)
        for i in range(Q):
            if h[a[i]]-h[b[i]]==c[i]:
                s+=d[i]
    if o<s:
        o=s
print(o)

Submission status: Runtime Error

Solution code:

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

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

A = [0]*60

    

l = [0]*60
for z in range(60):
  x = 0
  for j in range(q - 1):
    if A[z[b[j] - 1]] - A[z[a[j] - 1]] == c[j]:
      x = x + int(d[j])
    l[j] = x
    
    
x = 0
for j in range(q - 1):
  if A[b[j] - 1] - A[a[j] - 1] == c[j]:
    x = x + int(d[j])
  l[j] = x

print(max(l))

Submission status: Runtime Error

Solution code:
import bisect

def lis(lst):
    lis_lst = [lst[0]]
    for i in lst:
        if i > lis_lst[-1]:
            lis_lst.append(i)
        else:
            lis_lst[bisect.bisect_left(lis_lst, i)] = i
    return len(lis_lst)

n = int(input())

a = list(map(int, input().split()))

uv = {}
for _ in range(n-1):
    u, v = map(int, input().split())
    uv[v] = u
    
for i in range(1, n + 1):
    lst = []    
    while i != 1:
        lst.append(a[i - 1])
        i = uv[i]
    lst.append(a[0])
    lst.reverse()
    print(lis(lst))

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for j in range(q):
    a2,b2,c2,d2=map(int,input().split())
    a.append(a2)
    b.append(b2)
    c.append(c2)
    d.append(d2)

#dp[i][j] i番目までの数字でjまでつかってとれる最高得点
dp=[[0]*(m+1) for _ in range(n+1)]

for i in range(q):
    for k in range(m+1):
        if k+c>m:
            continue
        dp[b[i]][k+c]=dp[a[i]][k]+d[i]

ans = 0
for j in range(m):
    ans = max(ans,dp[n][j]) 
print(dp[n][m])

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

def check(A,n,m):
    if 1 <= A[0] and A[0] <= A[1] and A[1] <= A[2] and A[2] <= A[3] and A[3] <= m:
        flg = True
    else:
        flg = False
    return flg

def checkUpdate(A,B,n,m):
    if np.all(A[~(A==0)] == B[~(B==0)]):
        flg = True
    else:
        flg = False
    return flg

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

    A = [1 for i in range(n)]
    for k in range(m-1):
        A.extend([k+2 for i in range(n)])

    #print(A)

    ls = list(set(list(itertools.combinations(A, n))))
    #print(ls)
    points = np.zeros(len(ls))
    for i in range(len(ls)):
        A = ls[i]
        for i in range(q):
            ary = abcds[i]
            if A[ary[1]-1] == A[ary[0]-1] + ary[2]:
                points[i] += ary[3]


    print(np.max(points))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([1, 0], repeat=q):
    cnt = 0
    aaa = []
    aaaa = set()
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
            cnt += d
    if ans < cnt:
        for a, b, c in aaa:
            for aa, bb, cc in aaa[]:
                if aa == a and b < bb:
                    aaaa.add([b, bb, cc - c])
                elif aa == a and b > bb:
                    aaaa.add([bb, b, c - cc])
                if b == bb and aa > a:
                    aaaa.add([a, aa, cc - c])
                elif b == bb and aa < a:
                    aaaa.add([aa, a, c - cc])
        aaa += list(aaaa)
        flag = True
        for i, (a, b, c, d) in enumerate(abcd):
            if bit[i] == 1:
                for aa, bb, cc in aaa:
                    if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                        if aa == a and bb == b and c == cc:
                            continue
                        else:
                            flag = False
                            break
                if not flag:
                    cnt = 0
                    break
        if ans < cnt:
            ans = cnt
print(ans)

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(N):
    for j in range(i,N):
        for k in range(j,N):
            Ax.append([i+1,j+1,k+1])
            p+=1

for j in range(p):
    Dx=0
    for i in range(N):
        print(i,j)
        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:
# -*- coding: utf-8 -*-

import numpy as np
# スペース区切りの整数の入力

#def fanc(i,N):
#    if i==N:



N, M, Q = map(int, input().split())
# 文字列の入力
#s = input()
#開業されたN個要素を受け付ける
list = [input().split() for i in range(Q)]
f = np.vectorize(int)
list = f(list)
list = sorted(list, key=lambda x: x[3])
#print(list)
#list = sorted(list, reverse=True, key=lambda x: x[3])
A=[]
for i in range(N):
    A.append(1)
#while(A[-1]<=10):
    #print(A)
#    A[-1]=A[-1]+1
#print(A)
for i in range(Q):
    for j in range(len(list)):
        if A[list[j][0]-1] + list[j][2] <= M:
            tmp = A[list[j][1]-1]
            A[list[j][1]-1] = A[list[j][0]-1] + list[j][2]
        if not A == A.sorted():
            A[list[j][1]-1] = tmp
        #print(A)
sum=0
for i in range(len(list)):
    if A[list[i][1]-1] == A[list[i][0]-1] + list[i][2]:
        sum = sum + list[i][3]
        #print(sum)

print(sum)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m, q = map(int, input().split())
x = [[] for i in range(q)]
for i in range(q):
    x[i] = list(map(int, input().split()))
x.sort(reverse=True, key=lambda x:x[3])
# print(x)
ans = 0
r = [-1 for i in range(n)]
nums = [0 for i in range(m)]
for i in range(q):
    ai = x[i][0]
    bi = x[i][1]
    ci = x[i][2]
    di = x[i][3]
    if r[ai - 1] != -1:
        if r[bi - 1] != -1:
            continue
        if nums[r[ai - 1] + ci - 1] == 0:
            if bi != n and r[bi - 2] > r[ai - 1] + ci:
                continue
            if r[ai - 1] + ci > r[bi]:
                continue                
            ans += di
            r[bi - 1] = r[ai - 1] + ci
            nums[r[ai - 1] + ci - 1] = 1
            continue
        else:
            continue
    if r[bi - 1] != -1:
        if nums[r[bi - 1] - ci - 1] == 0:
            if ai != 1 and r[ai - 2] > r[bi - 1] - ci:
                continue
            if r[bi - 1] - ci > r[ai]:
                continue
            ans += di
            r[ai - 1] = r[bi - 1] - ci
            nums[r[bi - 1] - ci - 1] = 1
            continue
        else:
            continue
    for j in range(1, m + 1):
        flag = False
        for k in range(j, m + 1):
            if k - j != ci:
                continue
            if nums[j - 1] == 1 or nums[k - 1] == 1:
                continue
            if ai != 1 and r[ai - 2] != -1 and r[ai - 2] > j:
                continue
            if r[ai] != -1 and j > r[ai]:
                continue
            if r[bi - 2] != -1 and r[bi - 2] > k:
                continue
            if bi != n and r[bi] != -1 and k > r[bi]:
                continue
            ans += di
            nums[j - 1] = 1
            nums[k - 1] = 1
            r[ai - 1] = j
            r[bi - 1] = k
            flag = True
            break
        if flag:
            break
    print("r =", r)
    print("nums =", nums)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def nap(abcd, i, array, score, m, q):
    if i == q:
        up = n
        bottom = 1
        while array[up] == 0:
            up -= 1
        while array[bottom] == 0:
            bottom += 1
        if array[up] - array[bottom] >= m:
            return -1
        else:
            return score
    else:
        a, b, c, d = abcd[i]
        if array[a] == 0 or array[a] == array[b] - c:
            array[a] = array[b] - c
            score2 = nap(abcd, i+1, array, score+d, m, q)
        else:
            score2 = nap(abcd, i+1, array, score, m, q)
        if array[b] == 0 or array[b] == array[a] + c:
            array[b] = array[a] + c
            score1 = nap(abcd, i+1, array, score+d, m, q)
        else:
            score1 = nap(abcd, i+1, array, score, m, q)

        if score1 > score2:
            return score1
        else:
            return score2


n, m, q = map(int, input().split())
abcd = []
array = [0 for _ in range(n+1)]
for i in range(q):
    abcd.append(tuple(map(int, input().split())))
abcd.sort(reverse=True, key=lambda temp: temp[3])
print(nap(abcd, 0, array, 0, m, q))

Submission status: Runtime Error

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

a=[0 for _ in range(Q+1)]
b=[0 for _ in range(Q+1)]
c=[0 for _ in range(Q+1)]
d=[0 for _ in range(Q+1)]

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

def asc(x):
  y = sorted(x)
  return list(x)==y

def cond(p,i):
  if asc(p):
    try:
      if p[b[i]] - p[a[i]] == c[i]:
         # print(p)
         # print('{}-{}={} | d={}'.format(p[a[i]],p[b[i]],c[i],d[i]))
         return d[i]
    except IndexError:
        return 0
  return 0

import itertools
lisM=list(range(1,M+1))
print(lisM)
p = itertools.permutations(lisM, N+1)
D=[]
for x in p:
  for i in range(1,Q+1):
     D+=[cond(x,i)]
      
print(max(D))

Submission status: Runtime Error

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

n=0
for i in range(N):
    n+=int(10**i)
m=0
for i in range(N):
    m+=int(M*10**i)
ans=[]
for j in range(n,m):
    J=str(j)
    total=[]
    for k in range(Q):
        if int(J[S[k][1]-1])-int(J[S[k][0]-1])==int(S[k][2]):
            total.append(int(S[k][3]))
    ans.append((sum(total)))
    
ans=sorted(ans,reverse=True)  
print(ans[0])

Submission status: Runtime Error

Solution code:
import itertools
ml = []
a, b, c= map(int, input().split())
for i in range(c):
    ta,tb,tc,td=map(int, input().split())
    ml.append([ta,tb,tc,td])

pms = []
ok = True
for v in itertools.combinations_with_replacement(range(1,b+1),a):
    for i in range(a-1):
        if v[i+1]<v[i]:
            ok = False
            break
    if ok: pms.append(v)
    ok = True

s=0
sc=[]
for i in pms:
    for j in ml:
        if i[j[1]]-i[j[0]]==j[2]:
            s += ml[4]
    sc.append(s)
    s=0
print(max(sc))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time



def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def rec(li, i, M, N, a, b, c, d, cans):
    # print(i, li, len(li), N)
    if len(li) >= N:
        # print(li, N)
        ans = 0
        for j in range(len(a)):
            if li[b[j]-1] - li[a[j]-1] == c[j]:
                ans += d[j]
        # print(ans, li)
        return ans

    # for j in range(1, len(lis[i])):
    #     for v in lis[i][j]:

    ans = 0
    if len(cans[i]) == 0:
        ans = max(ans, rec(li + [1], i+1, M, N, a, b, c, d, cans))
    else:
        for v in cans[i]:
            ans = max(ans, rec(li + [v], i+1, M, N, a, b, c, d, cans))

    return ans


def main():
    N, M, Q = MI()
    a = [0] * Q
    b = [0] * Q
    c = [0] * Q
    d = [0] * Q
    didx = [None] * Q
    lis = [[[] for i in range(N+1)] for i in range(N+1)]
    cans = [set() for i in range(N+1)]

    for i in range(Q):
        a[i], b[i], c[i], d[i] = MI()
        # didx[i] = (d[i], i)

    # cans = []
    # for i in range(1, M+1):
    #     cans += [i] * N

    # for li in combinations(cans, N):
    #     print(li)

    # didx.sort(reverse=True)

    for i in range(Q):
        # lis[b[i]][a[i]].append(c[i])
        lis[a[i]][b[i]].append(c[i])

    for i in range(1, M):
        cans[i].add(1)

    for i in range(1, N+1):
        # print(i, lis[i])
        for j in range(len(lis[i])):
            for k in lis[i][j]:
                for v in cans[i]:
                    # print(v, k)
                    if v + k <= M:
                        cans[j].add(v + k)
    # print(cans)
    # print(didx)
    print(rec([], 1, M, N, a, b, c, d, cans))
    # print(sum(d))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools
n,m,q = map(int,input().split())
l = []
for i in range(q):
  l.append(list(map(int,input().split())))
j = [i for i in range(1,m+1)]
k = itertools.permutations(j, n)
for i in range(q):
  if k[l[i][1]]-k[l[i][0]] == l[i][2]:
    count += l[i][3]

Submission status: Runtime Error

Solution code:
import itertools
n,m,q=map(int,input().split())
qs = [list(map(int,input().split())) for i in range(q)]
mids = [i for i in range(m)]
# print(nums)
max_ans= 0
for mid in itertools.combinations_with_replacement(nums, n-1):
    if sum(mid)>m-1:
        continue
    sum_ans=0
    for i in qs:
        sum_mid = 0
        for j in range(i[0]-1,i[1]-1):
            sum_mid += mid[j]
        if sum_mid == i[2]:
            sum_ans += i[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)

Submission status: Runtime Error

Solution code:
n,m,q = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(q)]
import numpy as np
from itertools import combinations
num_list = np.arange(1,m+1)
suretsu = list(combinations(num_list, n))
wa = 0
wa_list= []
print(suretsu[1][1])

for i in range(q):
    a = data[i][0]
    b = data[i][1]
    c = data[i][2]
    d = data[i][3]
    print(a)
    print(c)
    for j in range(len(suretsu)):
        if suretsu[j][b-1] - suretsu[j][a-1] == c:
            wa = 0
            wa += d
            wa_list.append(wa)
ma = max(wa_list) 
print(ma)