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:
from collections import defaultdict
from itertools import product, combinations
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

cand = [[1]]
for i in range(M-1):
    tmp = []
    while cand:
        x = cand.pop()
        for i in range(x[-1], M + 1):
            tmp.append(x + [i])
    cand = tmp

ans = 0
for X in cand:
    score = 0
    for a, b, c, d in abcd:
        if X[b - 1] - X[a - 1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Runtime Error

Solution code:

import itertools
def q3():
    N, M, Q = [int(i) for i in input().split(" ")]
    l = []
    for i in range(Q):
        l.append([int(i) for i in input().split(" ")])

    num_elements = []
    for i in range(1, M + 1):
        num_elements.append(i)
    c = itertools.combinations_with_replacement(num_elements, N)
    As = []
    for v in c:
        if v[0] <= v[1] <= v[2]:
            As.append(list(v))

    
    max_point = 0
    for a in As:
        point = 0
        for vals in l:
            if a[vals[1] - 1] - a[vals[0] - 1] == vals[2]:
                point += vals[3]
        max_point = max(max_point, point)

    print(max_point)

q3()

Submission status: Runtime Error

Solution code:
N, M, Q = map(int,input().split())
L = []
def dfs(List):
    if len(List) == N - 1:
        L.append([0] + List)
    else:
        k = List[-1]
        for i in range(M-k):
            n_L = List[:]
            n_L.append(k+i)
            dfs(n_L)
for i in range(M):
    dfs([i])

MAX = 0
for l in L:
    cnt = 0
    for _ in range(Q):
        a, b, c, d = map(int,input().split())
        if l[b-1] - l[a-1] == c:
            cnt += d
    MAX = max(cnt, MAX)
print(MAX)

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):
    score = 0
    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:
n, m, q = map(int, input().split())
cnt = 0
for _ in range(q):
    a, b, c, d = list(map(int, input().split()))
for i in range(m-n+1):
    if b[i] - a[i] + (m-n) == c[i]:
        cnt += d[i]
print(cnt)

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(abcd)
print(nap(abcd, 0, array, 0, m, q))

Submission status: Runtime Error

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


A_list = []
N=2
for i in range(10**(N-1),10**N):
    #A = [int(x) for x in list(str(i))]
    #A_replace = [int(str(a).replace('0', '10')) for a in A]
    #if A_replace == sorted(A_replace):
    A_list.append(sorted(str(i)))
abcd_list = []
for q in range(Q):
    abcd_list.append(list(map(int, input().split())))

for A in A_list:
    tokuten = 0
    for q in range(Q):
        if (A[abcd_list[q][1]-1] - A[abcd_list[q][0]-1] == abcd_list[q][2]):
            tokuten += abcd_list[q][3]

    if tokuten > max_n:
        max_n = tokuten

print(max_n)

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-2]
print(sum(dd))

Submission status: Runtime Error

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

#qは組みの数
#Nは長さ
#Mは値
MM = [1,2,3,4,5,6,7,8,9,10]
a=[]
b=[]
c=[]
d=[]

xy = [map(int, input().split()) for _ in range(Q)]
a,b,c,d = [list(i) for i in zip(*xy)]

for i in range(10, M,-1):
	MM.pop(i-1)
	print(MM) 
for j in range(2, N,1):
	MM.pop(j-1)
	print(MM) 
for k in rage(len(a):
	if MM[b[k]]-MM[a[k]] = c[k]:
	anser += answer
print(answer)

Submission status: Runtime Error

Solution code:
import itertools

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

def solution(n):
    for p in itertools.product((0, 1), repeat=n):
        yield (0,) + tuple(itertools.accumulate(p))
maxx = 0
for p in solution(M):
    sum = 0
    for j in range(Q):
        if p[b[j] - 1] - p[a[j] - 1] == c[j]:
            sum += d[j]
    maxx = max (sum, maxx)
print (maxx)

Submission status: Runtime Error

Solution code:
import math
def solve():
    n, m, q = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(q)]

    ans = 0
    for i in range(2**(n-2)):
        cur = []
        for j in range(n-2):
            if (i>>j)&1:
                cur.append(i+1)
        A = [1] + cur + [n, m]
        print(A)
        tot = 0
        for k in range(q):
            a, b, c, d = l[k]
            if b+1 <= n and A[b] - A[a] == c:
                print(A[0], A[a])
                tot += d
        ans = max(ans, tot)
    
    return ans


print(solve())

Submission status: Runtime Error

Solution code:
import sys;
s = list(map(int,input().split()));
n = s[0];
m = s[1];
q = s[2];
count = 0;
sum = 0;
max = 0;
b = [input().split() for l in range(q)];
j = 0;
for i in range(q):
    sum = 0;
    for i in range(m):
        a = [];
        for i in range(n):
            a.append(j);
        j += 1;
        if(a[1] - a[0] == a[2]):
            sum += a[3];
    if(max <= sum):
        max = sum;


print(max);

Submission status: Runtime Error

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

def ans(A, M):
    lista = []
    l = len(A)
    for i in range(0,len(A)):
        for j in range(A[i][-1], M+1):
            listb = A[i].copy()
            listb.append(j)
            A.append(listb)
    A = A[l:]
    return A

B = []
for i in range(Q):
    lista = list(map(int,input().split()))
    B.append(lista)
    
maxSum = 0

A = [[i] for i in range(1,N+1)]
for i in range(N):
    A = ans(A, M)

    
c = 0


for As in A:
    Sum = 0
    for i in range(Q):
        if As[B[i][1]] - As[B[i][0]] == As[B[i][2]]:
            Sum += As[B[i][3]]
        
    maxSum = max(maxSum, Sum)

print(maxSum)

Submission status: Runtime Error

Solution code:
import itertools
x = input().split()
n = int(x[0])
m = int(x[1])
q = int(x[2])
s = [input().split() for i in range(q)]
l = []
count = 0
for i in range(1, m+1):
  l.append(i)
count_l = 0
for A in itertools.permutations(l, n):
  for i in range(0, q):
    a = int(s[i][0])-1
    b = int(s[i][1])-1
    c = int(s[i][2])
    d = int(s[i][3])
    if A[0] < A[1] and A[1] < A[2]:
      if A[b] - A[a] == c:
        count += d
  if count > count_l:
    count_l = count
  count = 0
print(count_l)

Submission status: Runtime Error

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

###
# main
if(__name__ == '__main__'):
    # input
    n, m, q = map(int, input().split(" "))
    dic = {}
    for _ in range(q):
        a, b, c, d = map(int, input().split(" "))
        dic[a, b, c] = d

    ans = 0
    a = []
    base = 1
    for i in range(q):
        if i == 0:
            a.append(1)
            continue
        else:
            max = 0
            max_tgt = m
            for tgt in range(base,m+1):
                point = 0
                for r in range(len(a)):
                    tgt_list = [r+1, i+1, tgt-a[r]]
                    if tgt_list in dic:
                        point += dic[tgt_list]
                if max < point:
                    max = point
                    max_tgt = tgt
            a.append(max_tgt)
            ans += max
            base = max_tgt

    print(ans)
# else:
    # do nothing

Submission status: Runtime Error

Solution code:
import itertools

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

abcd = []

for _ in range(q):
	abcd.append(list(map(int,input().split())))

abcd = sorted(abcd, key=lambda x:x[3],reverse=True)
l = [-1 for _ in range(n)]
tmp = 0
ans = 0
#print(abcd)
for a,b,c,d in abcd:
	a -= 1
	b -= 1
	minimum = 11
	maximum = 0
	for i in range(a):
		if l[i] != -1:
			mininum = min(minimum,l[i])
	if minimum == 11:
		minimum = 1
	for i in range(b+1,n):
		if l[i] != -1:
			maximum = max(maximum,l[i])
	if maximum == 0:
		maximum = m
	if l[a] == -1 and l[b] == -1:
		if minimum + c <= maximum:
			l[a] = minimum
			l[b] = minimum + c
			tmp += d
	elif l[a] == -1:
		num = max(l[:a])
		if l[b] - c >= minimum:
			l[a] = l[b] - c
			tmp += d
	elif l[b] == -1:
		if l[a] + c <= maximum:
			l[b] = l[a] + c
			tmp += d
	else:
		if l[b] - l[a] == c:
			tmp += d
	#print(tmp)
	ans = max(ans,tmp)

print(ans)

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]-v[a]==c:
      ans+=d
  ansl.append(ans)
print(max(ansl))

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

score = 0
for _t in t:
    _s = 0
    _t = list(_t)
    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:
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)

s = sum(l[:][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)
    if mscore == s:
        break

print(mscore)

Submission status: Runtime Error

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


A_list = []
N=2
for i in range(10**(N-1),10**N):
    #A = [int(x) for x in list(str(i))]
    #A_replace = [int(str(a).replace('0', '10')) for a in A]
    #if A_replace == sorted(A_replace):
    A_list.append(sorted(i))
abcd_list = []
for q in range(Q):
    abcd_list.append(list(map(int, input().split())))

for A in A_list:
    tokuten = 0
    for q in range(Q):
        if (A[abcd_list[q][1]-1] - A[abcd_list[q][0]-1] == abcd_list[q][2]):
            tokuten += abcd_list[q][3]

    if tokuten > max_n:
        max_n = tokuten

print(max_n)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
s =[ list(map(int,input().split())) for i in range(q)]
A = [i for i in range(1,m+1)]
ans = 0
alist = [0]*n
alist[0] = 1
for i in range(q):
    if s[i][1] - s[i][0] <= s[i][2]:
        alist.insert(s[i][1]-1,s[i][0]+s[i][2])
        alist = list(set(alist)).remove(0)
for i in range(q):
    if alist[s[i][1]] - alist[s[i][0]] == s[i][2]:
        ans += s[i][3]

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

abcd = []

for _ in range(q):
	abcd.append(list(map(int,input().split())))

abcd = sorted(abcd, key=lambda x:x[3],reverse=True)
l = [-1 for _ in range(n)]
tmp = 0
ans = 0
print(abcd)
for a,b,c,d in abcd:
	a -= 1
	b -= 1
	minimum = 11
	maximum = 0
	for i in range(a):
		if l[i] != -1:
			mininum = min(minimum,l[i])
	if minimum == 11:
		minimum = 1
	for i in range(b+1,n):
		if l[i] != -1:
			maximum = max(maximum,l[i])
	if maximum == 0:
		maximum = m
	if l[a] == -1 and l[b] == -1:
		if minimum + c <= maximum:
			l[a] = minimum
			l[b] = minimum + c
			tmp += d
	elif l[a] == -1:
		num = max(l[:a])
		if l[b] - c >= minimum:
			l[a] = l[b] - c
			tmp += d
	elif l[b] == -1:
		if l[a] + c <= maximum:
			l[b] = l[a] + c
			tmp += d
	else:
		if l[b] - l[a] == c:
			tmp += d
	#print(tmp)
	ans = max(ans,tmp)

print(ans)

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

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
# N, M, Q = 4, 6, 10


Qi = np.zeros((Q, 4), dtype='int64')
# Qi = np.zeros((Q, 4))

# listSample = []
# listSample.append("2 4 1 86568")
# listSample.append("1 4 0 90629")
# listSample.append("2 3 0 90310")
# listSample.append("3 4 1 29211")
# listSample.append("3 4 3 78537")
# listSample.append("3 4 2 8580")
# listSample.append("1 2 1 96263")
# listSample.append("1 4 2 2156")
# listSample.append("1 2 0 94325")
# listSample.append("1 4 3 94328")



for i in range(Q):
    Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,input().split())

   
# for i in range(Q):
#     Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,listSample[i].split())

Mr = np.max(Qi[2])+1

# Qi[0][0], Qi[0][1], Qi[0][2], Qi[0][3] = map(int,"1 3 3 100".split())
# Qi[1][0], Qi[1][1], Qi[1][2], Qi[1][3] = map(int,"1 2 2 10".split())
# Qi[2][0], Qi[2][1], Qi[2][2], Qi[2][3] = map(int,"2 3 2 10".split())


Mi = np.arange(1, min(M+1, Mr))
maxD = 0
for listMi in (list(combinations_with_replacement(Mi, N))):
    d = 0
    for i in range(Q):
        # if (int(listMi[int(Qi[i][1]-1)]-listMi[int(Qi[i][0]-1)]) == int(Qi[i][2])):
        if (listMi[Qi[i][1]-1]-listMi[Qi[i][0]-1] == Qi[i][2]):
            d += Qi[i][3]
    if d>maxD:
        maxD = d
        # print (listMi)
print (int(maxD))

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement

n, m, q = map(int,input().split())
l = []
s = []
for _ in range(q):
    a, b, c, d = map(int,input().split())
    l.append([a, b, c, d])

ps = list(combinations_with_replacement(range(2, m+1), n-1))
n_p = len(ps)

for i in range(n_p):
    ns = [1] + list(ps[i])
    ss = 0
    for j in range(q):
        k = l[j]
        if ns[k[1]-1] - ns[k[0]-1] == k[2]:
            ss += k[3]
    s.append(ss)

print(max(s))

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
lis = [[] for _ in range(Q)]
for i in range(Q):
    lis[i] = list(map(int, input().split()))
G = 0
if N == 2:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            A = [a1, a2]
            P = 0
            for j in range(Q):
                if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                    P += lis[j][3]
            if P > G:
                G = P
    print(G)
if N == 3:
   for a1 in range(M):
       for a2 in range(M-a1+1):
           for a3 in range(M-a2+1):
                A = [a1, a2, a3]
                P = 0
                for j in range(Q):
                    if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                        P += lis[j][3]
                if P > G:
                    G = P
    print(G)
if N == 4:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    A = [a1, a2, a3, a4]
                    P = 0
                    for j in range(Q):
                        if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                            P += lis[j][3]
                    if P > G:
                        G = P
    print(G)
if N == 5:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        A = [a1, a2, a3, a4, a5]
                        P = 0
                        for j in range(Q):
                            if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                P += lis[j][3]
                        if P > G:
                            G = P
    print(G)
if N == 6:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        for a6 in range(M-a5+1):
                            A = [a1, a2, a3, a4, a5, a6]
                            P = 0
                            for j in range(Q):
                                if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                    P += lis[j][3]
                            if P > G:
                                G = P
    print(G)
if N == 7:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        for a6 in range(M-a5+1):
                            for a7 in range(M-a6+1):
                                A = [a1, a2, a3, a4, a5, a6, a7]
                                P = 0
                                for j in range(Q):
                                    if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                        P += lis[j][3]
                                if P > G:
                                    G = P
    print(G)
if N == 8:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        for a6 in range(M-a5+1):
                            for a7 in range(M-a6+1):
                                for a8 in range(M-a7+1):
                                    A = [a1, a2, a3, a4, a5, a6, a7, a8]
                                    P = 0
                                    for j in range(Q):
                                        if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                            P += lis[j][3]
                                    if P > G:
                                        G = P
    print(G)
if N == 9:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        for a6 in range(M-a5+1):
                            for a7 in range(M-a6+1):
                                for a8 in range(M-a7+1):
                                    for a9 in range(M-a8+1):
                                        A = [a1, a2, a3, a4, a5, a6, a7, a8, a9]
                                        P = 0
                                        for j in range(Q):
                                            if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                                P += lis[j][3]
                                        if P > G:
                                            G = P
    print(G)
if N == 10:
    for a1 in range(M):
        for a2 in range(M-a1+1):
            for a3 in range(M-a2+1):
                for a4 in range(M-a3+1):
                    for a5 in range(M-a4+1):
                        for a6 in range(M-a5+1):
                            for a7 in range(M-a6+1):
                                for a8 in range(M-a7+1):
                                    for a9 in range(M-a8+1):
                                        for a10 in range(M-a9+1):
                                            A = [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
                                            P = 0
                                            for j in range(Q):
                                                if A[lis[j][1]] - A[lis[j][0]] == lis[j][2]:
                                                    P += lis[j][3]
                                            if P > G:
                                                G = P
    print(G)

Submission status: Runtime Error

Solution code:
from itertools import product

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

A = [0, 1]
combnation = list(product(A, repeat=N))
abcd.sort()

ans = 0
for comb in combnation:
    comb_list = [abcd[i] for i, k in enumerate(comb) if k==1]
    check = True
    A = [0 for i in range(N+1)]
    amount = 0
    for a, b, c, d in comb_list:
        amount += d
        if A[a] == 0 and A[b] == 0:
            if A[a] == 0 and A[b] == 0:
                A[a] = 1
                A[b] = 1 + c
    
        elif A[a] == 0 and A[b] != 0:
            if A[b] - c >= 1:
                A[a] = A[b] - c
            else:
                check = False
    
        elif A[a] != 0 and A[b] == 0:
            if c + A[a] <= M:
                A[b] = A[a] + c
            else:
                check = False
        else:
            if A[b] - A[a] != c:
                check = False
        
    
    if check and amount > ans:
        ans = amount
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
def main():
    N,M,Q = map(int,input().split())
    q = []
    for i in range(Q):
        a,b,c,d = map(int,input().split())
        q.append([a-1,b-1,c,d])
    A = [i for i in range(1,M+1)]
    if N==10:

        ans = 0
        for i, qq in enumerate(q):
            if A[qq[1]] - A[qq[0]] == qq[2]:
                ans += qq[3]
        print(ans)

    else:
        aa = list(itertools.combinations(A,N))
        ans = 0

        for i, cc in enumerate(aa):
            ans1 = 0
            for j, qq in enumerate(q):
                if cc[qq[1]] - cc[qq[0]] == qq[2]:
                    ans1 += qq[3]
            # print(ans1,cc)
            ans = max(ans,ans1)
        print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, Q = map(int, input().split())
    R = [list(map(int, input().split())) for i in range(Q)]
    ARR = [0]*N
    SUM = 0
    ANS = 0
    for i in nums:
        if ARR[R[i][0]-1] != 0:
            A = ARR[R[i][0]-1] 
        else:
            ARR[R[i][0]-1] = 1 
            A = ARR[R[i][0]-1] 
        if ARR[R[i][1]-1] != 0:
            B = ARR[R[i][1]-1]
        else:
            ARR[R[i][1]-1] = ARR[R[i][0]-1] + R[i][2]
        if ARR[R[i][1]-1]-ARR[R[i][0]-1] == R[i][2]:
            SUM += R[i][3]
        if max(ARR) - min(ARR) <= M:
            ANS = max(ANS, SUM)
        SUM = 0
    print(ANS)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools

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

QList = []

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

answers2 = []
answers = []

for A in list(itertools.permutations(range(M + 1),N)):
    status = True
    count = 1
    for i in A:
        if i < count:
            status = False
            break
    answers = []
    if status == True:
        for temp in QList:
            try:
                if A[temp[1]] - A[temp[0]] == temp[2]:
                    answers.append(temp[3])
            except:
                pass
    answers2.append(sum(answers))

print(max(answers2))

Submission status: Runtime Error

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

###
# main
if(__name__ == '__main__'):
    # input
    n, m, q = map(int, input().split(" "))
    dic = {}
    for _ in range(q):
        a, b, c, d = map(int, input().split(" "))
        dic[a, b, c] = d

    ans = 0
    a = []
    base = 1
    for i in range(q):
        if i == 0:
            a.append(1)
            continue
        else:
            max = 0
            max_tgt = m
            for tgt in range(base,m+1):
                point = 0
                for r in range(len(a)):
                    if [r+1, i+1, tgt-a[r]] in dic:
                        point += dic[r+1, i+1, tgt-a[r]]
                if max < point:
                    max = point
                    max_tgt = tgt
            a.append(max_tgt)
            ans += max
            base = max_tgt

    print(ans)
# else:
    # do nothing

Submission status: Runtime Error

Solution code:
import itertools
def main():
    N,M,Q = map(int,input().split())
    q = []
    for i in range(Q):
        a,b,c,d = map(int,input().split())
        q.append([a-1,b-1,c,d])
    A = [i for i in range(1,M+1)]
    if N==10:

        ans = 0
        for i, qq in enumerate(q):
            if A[qq[1]] - A[qq[0]] == qq[2]:
                ans += qq[3]
        print(ans)

    else:
        aa = list(itertools.combinations(A,N))
        ans = 0
        
        for i, cc in enumerate(aa):
            ans1 = 0
            for j, qq in enumerate(q):
                if cc[qq[1]] - cc[qq[0]] == qq[2]:
                    ans1 += qq[3]
            print(ans1,cc)
            ans = max(ans,ans1)
        print(ans)

if __name__=='__main__':
    main()

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





def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))



All =[0] * M
for i in range(M):
    All[i] = i+1

#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。



#M個のうちからN個取り出す順列
ans = 0
for A in itertools.product(All, N):
    #点数計算
    print(A)
    wa = 0
    for i in range(Q):
        print(wa) 
        kari = A[b[i]-1] - A[a[i]-1]
        if kari == c[i]:
            wa = wa + d[i] 
    if ans < wa:
        ans = wa
    #print(ans) 
    #print(wa) 


print(ans)

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)


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:
N, M, Q = map(int, input().split())
q_list = []

for i in range(Q):
    n_list = [int(x) for x in input().split()]
    q_list.append(n_list)

A_list = []
for i in range(1, M):
    A_init = []
    for j in range(N):
        A_init.append(i)
    while A_init[0] < M:
        for k in range(N):
            while A_init[-1-k] < M:
                A_true = A_init.copy()
                A_list.append(A_true)
                A_init[-1-k] = A_init[-1-k] + 1
A_fin = []
for i in range(N):
    A_fin.append(M)
A_list.append(A_fin)

tem_max = 0
for A in A_list:
    q_max = 0
    for q in q_list:4 6 10
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            q_max += q[3]
    if tem_max < q_max:
        tem_max = q_max
print(tem_max)

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-1] - T[a-1] == c:
            score += d
    SC.append(score)
    score = 0
#print(SC)
print(max(SC))

Submission status: Runtime Error

Solution code:
import itertools

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

for i  in range(q):
    a[i],b[i],c[i],d[i]= map(int,input().split())
    
A=list(itertools.combinations([i for i in range(1,m+1)],n))

e=0

g=[]
for v in A:
    e=0
    for i in range(q):
        
        if v[b[i]-1]-v[a[i]-1] ==c[i]:
            e += d[i]
            
        
    g += [e]
print(max(g))

Submission status: Runtime Error

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

d=[[[0],0]]
for i in range(1,n):
  r=[[[],0]for i in range(m)]
  mk=0
  for j in d:
    for k in range(j[0][-1],m):
      s=0
      for a in l:
        if (i==a[1]-1)and(k-j[0][a[0]-1]==a[2]):
          s+=a[3]
      if r[k][1]<s+j[1]:
        r[k]=[j[0]+[k],s+j[1]]
  d=[]
  for rr in r:
    if len(rr[0]):
      d.append(rr)
print(max(list(map(lambda x:x[1],d))))

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:
            a = max(a, S[j:3])
        sum[i] = a

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

Submission status: Runtime Error

Solution code:
import itertools
N, M, Q = map(int,input().split())
s = [tuple(map(int, input().split())) for i  in range(Q)]
l = list(range(1,M+1))
ans = []
for v in itertools.combinations(l, N):
    new_v = sorted(v)
    count = 0
    for i in range(Q):
        a, b, c, d = s[i]
        if new_v[b-1] - new_v[a-1] == c:
            count += d
    ans.append(count)
print(max(0, max(ans)))