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: Wrong Answer

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

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


wa = 0
ans = 0

for i in itertools.product(list, repeat=n):
    for a,b,c,d in abcd:
        # print(a,b,c,d)
        # if a <= len(i) and b <= len(i):
        if i[b-1]-i[a-1]==c:
            wa += d
            ans = max(ans, wa)
    wa = 0

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

kouho = []
for i in range(1, m+1):
  kouho.append(i)
#print(kouho)

A = list(itertools.combinations(kouho,n))
#print(A)

point = 0
maxp = 0
for a in A:
  point = 0
  #print(a)
  for my in mylist:
    #print(my)
    if a[my[1]-1] - a[my[0]-1] == my[2]:
      point += my[3]
      print("yes")
  print(point)
  if point > maxp:
    maxp = point
    print("max更新")
    print(maxp)
print(maxp)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int, input().split())
score=0
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=[1]*N

for k in range(2,M+1):
    for l in reversed(range(N)):
        for m in range(2,k+1):
            A[l]=m
            temp=0
            for i in range(Q):
                if A[b[i]-1] - A[a[i]-1]==c[i]:
                    temp=temp+d[i]
            if temp>score:
                score=temp
    A=[1]*N
    A[N-1]=k
print(score)

Submission status: Wrong Answer

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

tmp = 0
mx = 0
for k in range(len(list)):
    #print(list[k])
    for i in range(Q):
        a = x[i][0]
        b = x[i][1]
        c = x[i][2]
        d = x[i][3]
        if(list[k][b-1] - list[k][a-1]) == c:
            tmp += d
        #print("{} {} {} {} {}".format(a,b,c,d,tmp))
    mx = max(mx,tmp)
    tmp = 0

print(mx)

Submission status: Wrong Answer

Solution code:
import copy
n, m, q = map(int, input().split())
point_table = []
tmp_ans = [1] * n


def check_point(tmp):
    ans_point = 0
    
    for k in point_table:
        if tmp[k[1] - 1] == k[2] + tmp[k[0] - 1]:
            ans_point += k[3]
    
    return ans_point


for i in range(q):
    point_table.append(list(map(int, input().split())))

point_table.sort(key=lambda row: row[3], reverse=True)

for j in point_table:
    new_ans = copy.copy(tmp_ans)
    new_ans[j[1] - 1] = j[2] + new_ans[j[0] - 1]
    
    if check_point(tmp_ans) <= check_point(new_ans):
        tmp_ans = new_ans
        
print(check_point(tmp_ans))

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
L = [list(map(int, input().split())) for i in range(Q)]
k = "1" * N
ans = 0
while k < str(M) * N:
  k = str(int(k) + 1)
  for i in range(N-1):
    if k[i] > k[i+1]:
      break
  else:
    A = 0
    for i in L:
      if int(k[i[1]-1]) - int(k[i[0]-1]) == i[2]:
        A += i[3]
    ans = max(A, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, M, Q = map(int, sys.stdin.readline().strip().split())
con = []  # condition
for i in range(Q):
    con.append(list(map(int, sys.stdin.readline().strip().split())))

dig = N + 1  # dig -1 桁の数字を作る
A = [1] * dig
point = 0


def make(min=1, digit=1):
    global point
    for i in range(min, 11):
        A[digit] = i
        if digit != dig - 1:
            make(min=i, digit=digit + 1)
        else:
            temp_point = 0
            for c in con:
                if A[c[1]] - A[c[0]] == c[2]:
                    temp_point += c[3]
            point = max(point, temp_point)


for i in range(1, 10):
    make(min=i, digit=1)

print(point)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import collections
# X = int(input())
N, M, Q = map(int, input().split())
As =[0]
Bs =[0]
Cs =[0]
Ds =[0]

for i in range(Q):
	a, b, c, d = map(int, input().split())
	As.append(a)
	Bs.append(b)
	Cs.append(c)
	Ds.append(d)

lst = range(1, M+1)
AAss = list(itertools.combinations(lst, N))

rCs = collections.Counter()
for i, c in enumerate(Cs):
	# print(i)
	rCs[c] = Ds[i]
max_score = 0
# print("rCs")
# print(rCs)
for AAs in AAss:
	score = 0
	# print("AAs")
	# print(AAs)
	AAs = [0] + list(AAs)
	# print(AAs)
	for i in range(1,Q+1):
		# print("AAs[Bs[i]] - AAs[As[i]]")
		# print(AAs[Bs[i]] - AAs[As[i]])
		score += rCs[AAs[Bs[i]] - AAs[As[i]]]
		# print("dif_score")
		# print(rCs[AAs[Bs[i]] - AAs[As[i]]])

	if score > max_score:
		max_score = score
	# print("score")
	# print(score)
print(max_score)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(200000)


def read():
    N, M, Q = map(int, input().split())
    ABCD = []
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        ABCD.append((a, b, c, d))
    return N, M, Q, ABCD


def check(N, M, Q, ABCD, x):
    score = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            score += d
    return score


def solve(N, M, Q, ABCD):
    smax = 0
    for a in range(M+1):
        for b in range(a, M+1):
            for c in range(b, M+1):
                for d in range(c, M+1):
                    for e in range(d, M+1):
                        for f in range(e, M+1):
                            for g in range(f, M+1):
                                for h in range(g, M+1):
                                    for i in range(h, M+1):
                                        for j in range(i, M+1):
                                            s = check(N, M, Q, ABCD, [a, b, c, d, e, f, g, h, i, j][:N])
                                            smax = max(s, smax)
    return smax


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))

Submission status: Wrong Answer

Solution code:
import itertools
N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []

for i in range(Q):
  aa, bb, cc, dd = list(map(int, input().split()))
  a.append(aa)
  b.append(bb)
  c.append(cc)
  d.append(dd)

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

res = 0
for s in itertools.combinations(Ms, N):
  sum_ = 0
  for j in range(Q):
    if s[b[j]-1] - s[a[j]-1] == c[j]:
      sum_ += d[j]
  if sum_ > res:
    res = sum_

print(res)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, Q = list(map(int, input().split(" ")))
abcd = []
sample = list(range(1,M+1))
for i in range(Q):
  abcd.append(list(map(int, input().split(" "))))
res = []
for A in itertools.combinations(sample, N):
  r = 0
  for a,b,c,d in abcd:
    if A[b-1] - A[a-1] == c:
      r += d
  res.append(r)
print(res)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

A = [x for x in range(1,M+1)]

max_score = 0
for a in itertools.combinations(A,N):
	score = 0
	for s in series:
		if (a[s[1]-1] - a[s[0]-1]) == s[2]:
			score += s[3]
			
	if score > max_score: max_score = score

print(max_score)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
S=[list(map(str,input().split())) for i in range(Q)]
result=0
count=0
A=[1]*N
for i in range(N):
    for j in range(1,M):
        A[i]+=1
        for s in S:
            if A[int(s[0])-1]-A[int(s[1])-1]==int(s[2]):
                count+=int(s[3])
        if result<count:
            result=count
        count=0
print(result)

Submission status: Wrong Answer

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions

t = stdin.readline().rstrip().split()
N = int(t[0])
M = int(t[1])
Q = int(t[2])

data = []
for el in range(Q):
    tt = stdin.readline().rstrip().split()
    a = int(tt[0])-1
    b = int(tt[1])-1
    c = int(tt[2])
    d = int(tt[3])
    data.append([a, b, c, d])

tes = 0
for pos in range(N):
    row = [1] * N
    res = 0
    check = False
    for el in data:
        if (row[el[1]] - row[el[0]]) == el[2]:
            continue
        else:
            if el[0] == pos:
                row[el[1]] = row[el[0]] + el[2]
            if el[1] == pos:
                row[el[0]] = row[el[1]] - el[2]
    for el in data:
        if (row[el[1]] - row[el[0]]) == el[2]:
            res += el[3]
    else:
        diffB = M - max(row)
        diffS = min(row)-1
        if min(row) + diffB >= 1:
            check = True
        if max(row) - diffS <= M:
            check = True
        if res > tes and check:
            tes = res

print(tes)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M, Q = mi()
abcd = li2(Q)

#N = 10

a = '0' * N

l = [a]
#for length in range(N):
while True:
    i = N-1
    while i >= 0 and a[i] == '9':
        i -= 1
    if i == -1:
        break
    a = list(a)
    num = str(int(a[i]) + 1)
    a[i] = num
    if i !=N-1:
        for j in range(i+1, N):
            a[j] = num
    tmp = ''.join(a)
    l.append(tmp)

ans = 0
for num in l:
    cnt = 0
    for i in range(Q):
        if int(num[abcd[i][1]-1]) - int(num[abcd[i][0]-1]) == abcd[i][2]:
            cnt += abcd[i][3]

    ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N, M, Q = map(int, input().split())
list_q = []
for i in range(Q):
    list_q.append(list(map(int, input().split())))
ans = 0

for A_ in itertools.combinations([i for i in range(1, M+1)], N):
    A = list(A_)
    tmp_ans = 0
    for i in range(Q):
        if A[list_q[i][1]-1] - A[list_q[i][0]-1] == list_q[i][2]:
            tmp_ans += list_q[i][3]
    if ans < tmp_ans:
        ans = tmp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(Q):
  all.append(list(map(int,input().split())))
#print(all)
#print(len(all))
#print(all[0][1])

x=sorted([i for i in range(1,M+1)]*4)
maxdsum=0


for A in itertools.combinations(x, N):
  dsum=0
  #print("A=="+str(A))
  for num in range(Q):
    if A[all[num][1]-1]-A[all[num][0]-1]==all[num][2]:
      dsum+=all[num][3]
  if maxdsum<dsum:
    maxdsum=dsum
print(maxdsum)

Submission status: Wrong Answer

Solution code:
import itertools

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


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

lis = [i for i in range(1,m+1)]
for pair in itertools.combinations(lis, n):
  a_pre.append(list(pair))

sum = 0
for i in range(len(a_pre)):
  sum_pre = 0
  for j in range(len(abcd)):
    if a_pre[i][abcd[j][1] - 1] - a_pre[i][abcd[j][0] - 1] == abcd[j][2]:
      sum_pre = sum_pre + abcd[j][3]
  if sum_pre > sum:
    sum = sum_pre

print(sum)

Submission status: Wrong Answer

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

import itertools
a = range(1, M+1)
for set_A in itertools.combinations_with_replacement(a, N):
    A = list(set_A)
    print(A)
    n = 0
    for i in range(Q):
        if A[b[i][1]-1] - A[b[i][0]-1] == b[i][2]:
            n += b[i][3]
    ans = max(ans, n)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split(" ")))
q_list = []
for v in range(q):
    qs = list(map(int, input().split(" ")))
    q_list.append(qs)
import itertools
seq=list(range(1, m+1))
l = list(itertools.permutations(seq, n))

check= 0

for s in range(len(l)):
    l_c = l[s]
    check_n = 0
    for v in range(q):
        q_check=q_list[v]
              
        if (l_c[q_check[1]-1] - l_c[q_check[0]-1] == q_check[2]):
            check_n = check_n +  q_check[3]   
    if check_n >= check:
        check=check_n
print(check)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
point=0
while Q>0:
  a,b,c,d=map(int,input().split())
  l=b-a+M-N
  s=b-a
  if c>=s and c<=l:
    point=point+d
  Q=Q-1
print(point)

Submission status: Wrong Answer

Solution code:
def make_arr(x, arr):
    if len(arr) == n:
        pattern.append(arr)
    else:
        for i in range(x, 11):
            make_arr(i, arr + [i])

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

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

ans = 0
for p in pattern:
    point = 0
    for a, b, c, d in query:
        a -= 1
        b -= 1
        if  (p[b] - p[a]) == c:
            point += d
    ans = max(ans, point)
print(ans)

Submission status: Wrong Answer

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


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

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

numbers = sorted(numbers , key = lambda x:-x[1])
numbers = sorted(numbers , key = lambda x:-x[0])
#print(numbers)

kouho = ["9"*(N)]
#print(kouho)
for a, b , c ,d in numbers:
    for k in kouho:
        if int(k[b-1]) - int(k[a-1]) != c:
            new_k = k[:a-1] + str(int(k[b-1])-c) +  k[a:]
            if int(k[b-1])-c >= 0:
                kouho.append(new_k)
                kouho = list(set(kouho))

#print(sorted(kouho))

answer = 0
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    if answer < ans:
        answer = ans
print(answer)
'''
kouho = []
for password in range(0,10**(N-1)):
    password = "9" + str(password).zfill(N-1)
    kouho.append(''.join(list(reversed(password))))

answers = [0] * len(kouho)
for i, k in  enumerate(kouho):
    ans = 0
    for a, b, c, d in numbers:
        if int(k[b-1]) - int(k[a-1]) == c:
            ans += d
    answers[i] = ans
print(max(answers))
'''

Submission status: Wrong Answer

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

ab.sort(key = lambda x: x[3],reverse=True)
ans = 0
sub = [0] * n
for i in range(q):
    if sub[ab[i][1] - 1] - sub[ab[i][0] - 1] == ab[i][2]:
        ans += ab[i][3]
    else:
        if sub[ab[i][0] - 1] == 0 or sub[ab[i][1] - 1] == 0:
            sub[ab[i][0] - 1] = 100000
            sub[ab[i][1] - 1] = sub[ab[i][0] - 1] + ab[i][2]
            ans += ab[i][3]

ans2 = 0
ab.sort(key=lambda x: x[2], reverse=True)
for i in range(q):
    if sub[ab[i][1] - 1] - sub[ab[i][0] - 1] == ab[i][2]:
        ans2 += ab[i][3]
    else:
        if sub[ab[i][0] - 1] == 0 or sub[ab[i][1] - 1] == 0:
            sub[ab[i][0] - 1] = 100000
            sub[ab[i][1] - 1] = sub[ab[i][0] - 1] + ab[i][2]
            ans2 += ab[i][3]

ans3 = 0
ab.sort(key=lambda x: x[1], reverse=True)
for i in range(q):
    if sub[ab[i][1] - 1] - sub[ab[i][0] - 1] == ab[i][2]:
        ans3 += ab[i][3]
    else:
        if sub[ab[i][0] - 1] == 0 or sub[ab[i][1] - 1] == 0:
            sub[ab[i][0] - 1] = 100000
            sub[ab[i][1] - 1] = sub[ab[i][0] - 1] + ab[i][2]
            ans3 += ab[i][3]



print(ans2)

Submission status: Wrong Answer

Solution code:
(n, m, q) = [int(s) for s in input().split()]

a = []
for _ in range(0, q):
    a.append([int(s) for s in input().split()])

sorted_a = sorted(a, key=lambda x: x[3], reverse=True)

ans = 0

tmp = [1] + ([9999] * (n - 2)) + [m]

for (a, b, c, d) in sorted_a:

    if tmp[a - 1] == 9999 and tmp[b - 1] == 9999:
        pass
    elif tmp[a - 1] == 9999:
        tmp[a - 1] = tmp[b - 1] - c
    elif tmp[b - 1] == 9999:
        tmp[b - 1] = tmp[a - 1] + c

    diff = tmp[b - 1] - tmp[a - 1]

    if diff == c:
        ans += d

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n,m,q=map(int,input().split())
    a=[]
    b=[]
    c=[]
    d=[]
    ans=0
    for i in range(q):
        ai,bi,ci,di=map(int,input().split())
        a.append(ai)
        b.append(bi)
        c.append(ci)
        d.append(di)
    indices = [*range(q)]
    sorted_indices = sorted(indices, key=lambda i: -d[i])
    sorted_num = [d[i] for i in sorted_indices]
    A=[1]*(n+1)
    for i in sorted_indices:
        #A[b[i]]-A[a[i]]=c[i]→A[b[i]=c[i]+A[a[i]]
        pre=A[b[i]-1]
        A[b[i]-1]=c[i]+A[a[i]-1]
        if A[b[i]]>m:
            break
        
        #All Check
        tmp=0
        for j in range(q):
            if A[b[j]-1]-A[a[j]-1]==c[j]:
                tmp+=d[j]
        if ans>tmp:
            A[b[i]-1]=pre
        ans=max(ans,tmp)
        
    print(ans)
    
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
input=stdin.buffer.readline

ip=[int(x) for x in input().split()]
n=ip[0]
m=ip[1]
q=ip[2]

ai=[]
bi=[]
ci=[]
di=[]
for i in range(q):
	ip=[int(x) for x in input().split()]
	ai.append(ip[0])
	bi.append(ip[1])
	ci.append(ip[2])
	di.append(ip[3])

if m<n:
	print(0)
else:
	a=[]
	if n==10:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							for i6 in range(i5,m+1):
								for i7 in range(i6,m+1):
									for i8 in range(i7,m+1):
										for i9 in range(i8,m+1):
											for i10 in range(i9,m+1):
												a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==9:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							for i6 in range(i5,m+1):
								for i7 in range(i6,m+1):
									for i8 in range(i7,m+1):
										for i9 in range(i8,m+1):
											a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==8:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							for i6 in range(i5,m+1):
								for i7 in range(i6,m+1):
									for i8 in range(i7,m+1):
										a.append([i1,i2,i3,i4,i5,i6,i7,i8])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==7:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							for i6 in range(i5,m+1):
								for i7 in range(i6,m+1):
									a.append([i1,i2,i3,i4,i5,i6,i7])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==6:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							for i6 in range(i5,m+1):
								a.append([i1,i2,i3,i4,i5,i6])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==5:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						for i5 in range(i4,m+1):
							a.append([i1,i2,i3,i4,i5])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==4:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					for i4 in range(i3,m+1):
						a.append([i1,i2,i3,i4])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==3:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				for i3 in range(i2,m+1):
					a.append([i1,i2,i3])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)
	elif n==2:
		for i1 in range(1,m+1):
			for i2 in range(i1,m+1):
				a.append([i1,i2])

		ans=0
		for i in range(len(a)):
			m=0
			for j in range(q):
				if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
					m+=di[j]
			if ans<m:
				ans=m

		print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
x=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
    for j in range(2):
        x[i][j]-=1
a=[]
def dfs(v):
    if len(v)>n:
        return
    if len(v)==n:
        a.append(v)
    for i in range(int(v[-1]),10):
        dfs(v+str(i))
for i in range(1,10):
    dfs(str(i))
ans=0
for i in a:
    now=0
    i=list(i)
    for k in range(n):
        i[k]=int(i[k])
    for k in range(q):
        if i[x[k][1]]-i[x[k][0]]==x[k][2]:
            now+=x[k][3]
    ans=max(now,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

max_val = 0
n = N
m = M
l = [i+1 for i in range(M)]
# print(l)
for v in itertools.combinations(l,n):
    # print(v)
    val = 0
    for q in range(Q):
        a = AA[q][0]-1
        b = AA[q][1]-1
        # print('a',a)
        # print('b',b)
        # print('lb',v[b])
        # print('la',v[a])
        # print('sabun',v[b]-v[a])
        # print('c',AA[q][2])
        if(v[b]-v[a] == AA[q][2]):
            val += AA[q][3]
            # print('add')
    # print(val)
    if val > max_val:
        max_val = val

print(max_val)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

max_val = 0
n = N
m = M
l = [i+1 for i in range(M)]
print(l)
for v in itertools.combinations(l,n):
    print(v)
    val = 0
    for q in range(Q):
        a = AA[q][0]-1
        b = AA[q][1]-1
        # print('a',a)
        # print('b',b)
        # print('lb',v[b])
        # print('la',v[a])
        # print('sabun',v[b]-v[a])
        # print('c',AA[q][2])
        if(v[b]-v[a] == AA[q][2]):
            val += AA[q][3]
            print('add')
    print(val)
    if val > max_val:
        max_val = val

print(max_val)

Submission status: Wrong Answer

Solution code:
import itertools

def resolve():
    N, M, Q = map(int, input().split())
    a_list = []
    b_list = []
    c_list = []
    d_list = []
    #A_list = [0 for i in range(N)]

    for i in range(Q):
        a, b, c, d = map(int, input().split())
        a_list.append(a)
        b_list.append(b)
        c_list.append(c)
        d_list.append(d)
    
    if 0 in c_list:
        main_list = list(itertools.product(range(1, M+1), repeat=N))
    else:
        main_list = list(itertools.permutations(range(1, M+1), N))

    max_sum = 0

    for sub_set in main_list:
        sum = 0
        for i in range(Q):
            if sub_set[b_list[i]-1] - sub_set[a_list[i]-1] == c_list[i]:
                sum += d_list[i]
        if max_sum <= sum:
            max_sum = sum

    print(max_sum)
    # 3 4 3 
    # 1 3 3 100
    # 1 2 2 10
    # 2 3 2 10

    # A = {1, 3, 4}
    # A_3 - A_1 = 3 => 100
    # A_2 - A_1 = 2 => 10
    # A_3 - A_2 = 1 => x



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools
def main():
# 整数の入力
    
    # スペース区切りの整数の入力
    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    q = s[2]
    t_list = []
    for i in range(q):
        s = [int(x) for x in input().split(' ')]
        t_list.append(s)

    seq = [x for x in range(1, m+1)]
    candidate_list = list(itertools.combinations(seq, n))

    candidate_d_list = []
    candidate_d_list.append(0)
    for candidate in candidate_list:
        d_list = []
        d_list.append(0)

        for t in t_list:
            a = t[0]
            b = t[1]
            c = t[2]
            d = t[3]
            
            if candidate[b-1] - candidate[a-1] == c:
                d_list.append(d)
        candidate_d_list.append(sum(d_list))

    
    print(max(candidate_d_list))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

nmq = list(map(int, input().split()))
n = nmq[0]
m = nmq[1]
q = nmq[2]
i = [list(map(int, input().split())) for i in range(q)]
a = list(range(1, m + 1))
a_all = list(itertools.combinations(a, n))
ans = 0
for x in a_all:
  val = 0
  for y in i:
    if x[y[1] - 1] - x[y[0] - 1] == y[2]:
      val += y[3]
  if val > ans:
    ans = val
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def ite(N, M):
    import itertools
    data = list(range(1, M+1, 1))
    return list(itertools.product(data, repeat=N))
  
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

N, M, Q = list(map(int, input().split(" ")))
li = []
for i in range(Q):
    li.append(list(map(int, input().split(" "))))

m_s = 0
li2 = ite(N, M) 
for l2 in li2:
#    if check(l2):
        s = score(l2, li)
        if m_s < s:
            m_s = s
            
print(m_s)

Submission status: Wrong Answer

Solution code:
from itertools import product
n, m, q =  list(map(int, input().split()))
aa = []
bb =[]
cc = []
dd =[]
for i in range(q):
    a,b,c,d =  list(map(int, input().split()))
    aa.append(a)
    bb.append(b)
    cc.append(c)
    dd.append(d)

def ev(A):
    s = 0
    for i in range(q):
        if A[bb[i] - 1] - A[aa[i] - 1] == cc[i]:
            s += dd[i]
    return s

A = [0] * n
s = ev(A)
for A in product(range(m), repeat=n):
    s = max([s, ev(A)])

print(s)