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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,Q = inputMap()
	A = []
	for i in range(Q):
		a,b,c,d = inputMap()
		A.append((a,b,c,d))

	retu = []
	for i1 in range(10,0,-1):
		tmp = []
		for i2 in range(10,0,-1):
			if i1 > i2:
				break
			for i3 in range(10,0,-1):
				if i2 > i3:
					break
				for i4 in range(10,0,-1):
					if i3 > i4:
						break
					for i5 in range(10,0,-1):
						if i4 > i5:
							break
						for i6 in range(10,0,-1):
							if i5 > i6:
								break
							for i7 in range(10,0,-1):
								if i6 > i7:
									break
								for i8 in range(10,0,-1):
									if i7 > i8:
										break
									for i9 in range(10,0,-1):
										if i8 > i9:
											break
										for i10 in range(10,0,-1):
											if i9 > i10:
												break
											tmp.append(i1)
											tmp.append(i2)
											tmp.append(i3)
											tmp.append(i4)
											tmp.append(i5)
											tmp.append(i6)
											tmp.append(i7)
											tmp.append(i8)
											tmp.append(i9)
											tmp.append(i10)
											retu.append(tmp[:N])
											tmp = []
	ans = 0

	for i in retu:
		#print(i)
		score = 0
		for vol in A:
			a,b,c,d = vol
			#print("{} {}".format(int(i[b-1]) - int(i[a-1]), c))
			if int(i[b-1]) - int(i[a-1]) == c:
				score += d

		if score > ans:
			ans = score

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
A=[]
i=1
while i<m-n+2:
    for a in range(i+1,m-n+3):
        if n==2:
            A.append([i,a])
        else:
            for b in range(a+1,m-n+4):
                if n==3:
                    A.append([i,a,b])
                else:
                    for c in range(b+1,m-n+5):
                        if n==4:
                            A.append([i,a,b,c])
                        else:
                            for d in range(c+1,m-n+6):
                                if n==5:
                                    A.append([i,a,b,c,d])
                                else:
                                    for e in range(d+1,m-n+7):
                                        if n==6:
                                            A.append([i,a,b,c,d,e])
                                        else:
                                            for f in range(e+1,m-n+8):
                                                if n==7:
                                                    A.append([i,a,b,c,d,e,f])
                                                else:
                                                    for g in range(f+1,m-n+9):
                                                        if n==8:
                                                            A.append([i,a,b,c,d,e,f,g])
                                                        else:
                                                            for h in range(g+1,n-m+10):
                                                                if n==9:
                                                                    A.append([i,a,b,c,d,e,f,g,h])
                                                                else:
                                                                    for j in range(h+1,n-m+11):
                                                                        A.append([i,a,b,c,d,e,f,g,h,j])
    i+=1
length=len(A)
if length==0:
    print(0)
else:
    l=[]
    ans=0
    for i in range(q):
        l.append(list(map(int,input().split())))
    for tmpA in A:
        tmp=0
        for tmpQ in l:
            if tmpA[tmpQ[1]-1]-tmpA[tmpQ[0]-1]==tmpQ[2]:
                tmp+=tmpQ[3]
        ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M,Q=map(int,input().split())
a=[]
for _ in range(Q):
    b=list(map(int,input().split()))
    a.append(b)
s=[]
for i in range(M+1):
    s.append(i)
alist=list(itertools.combinations(s, r=N+1))


tmp=0
for j in alist:
    s=0
    for i in range(Q):
        j=list(j)
        if j[a[i][1]]-j[a[i][0]]==a[i][2]:
            s+=a[i][3]
    tmp=max(tmp,s)
print(tmp)

Submission status: Wrong Answer

Solution code:
#create date: 2020-05-02 21:28

import sys
stdin = sys.stdin
from itertools import product

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m, q = na()
    l = list()
    for i in range(q):
        l.append(na())
    ans = 0
    for switch in product(range(1, m+1), repeat=n):
        switch = list(switch)
        print(switch)
        switch.sort()
        s = switch
        cnt = 0
        for a, b, c, d in l:
            a -= 1
            b -= 1
            if s[b] - s[a] ==c:
                cnt += d
        ans = max(cnt, ans)
    print(ans)

if __name__ == "__main__":
    main()

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]]
        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]
        ans=max(ans,tmp)
    print(ans)
    
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = [int(i) for i in input().split(" ")]
A = []
for i in range(q):
    A.append([int(i) for i in input().split(" ")])
given = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ans = itertools.combinations_with_replacement(given, 10)
answer = 0
ans = list(ans)
for solve in ans:
    now = 0
    for i in range(q):
        if (solve[A[i][1] - 1] - solve[A[i][0] - 1]) == A[i][2]:
            now += A[i][3]
    if (now > answer):
        answer = 0 + now
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from fractions import Fraction
# sys.setrecursionlimit(2*pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(" ".join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def recur(arr, cnt):
    if cnt == n and len(arr) == n:
        return findscore(arr)
    if cnt == n:
        return 0
    answer = 0
    for i in range(1, m+1):
        answer = max(answer, recur(arr, cnt+1), recur(arr+[i], cnt+1))
    return answer


def findscore(arr):
    score = 0
    for i in mat:
        a, b, c, d = i
        if arr[b-1] - arr[a-1] == c:
            score += d
    return score


n, m, q = sp()
mat = []
for i in range(q):
    mat.append(l())
out(recur([], 0))

Submission status: Wrong Answer

Solution code:
def permutationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _permutationWithRepetitionListRecursive(data, r, [], result)
  return result

def _permutationWithRepetitionListRecursive(data, r, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(len(data)):
    _permutationWithRepetitionListRecursive(data, r - 1, progress + [data[i]], result)

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

retsu = permutationWithRepetitionListRecursive(range(M), N)
result = 0

for i in retsu:
    score = 0
    for a in A:
        if i[a[1] - 1] - i[a[0] - 1] == a[2]:
            score += a[3]
    if result < score:
        result = score

print(result)

Submission status: Wrong Answer

Solution code:
import itertools

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

A = [[ int(n) for n in input().split()] for _ in range(Q) ]
n = [i for i in range(1,M+1)]
numbers = list(itertools.combinations_with_replacement(n, N))
ans = [0 for _ in range(len(numbers))]

q = Q
while  q> 0:
    q -= 1
    a, b, c, d = A[q][0], A[q][1], A[q][2], A[q][3]
    print(a,b,c,d)

    for i in range(len(numbers)):
        if numbers[i][b-1] - numbers[i][a-1] == c:
            ans[i] += d


print(max(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,Q = inputMap()
	A = []
	for i in range(Q):
		a,b,c,d = inputMap()
		A.append((a,b,c,d))

	retu = []
	for i1 in range(9,0,-1):
		tmp = []
		for i2 in range(9,0,-1):
			if i1 > i2:
				break
			for i3 in range(9,0,-1):
				if i2 > i3:
					break
				for i4 in range(9,0,-1):
					if i3 > i4:
						break
					for i5 in range(9,0,-1):
						if i4 > i5:
							break
						for i6 in range(9,0,-1):
							if i5 > i6:
								break
							for i7 in range(9,0,-1):
								if i6 > i7:
									break
								for i8 in range(9,0,-1):
									if i7 > i8:
										break
									for i9 in range(9,0,-1):
										if i8 > i9:
											break
										for i10 in range(9,0,-1):
											if i9 > i10:
												break
											tmp.append(i1)
											tmp.append(i2)
											tmp.append(i3)
											tmp.append(i4)
											tmp.append(i5)
											tmp.append(i6)
											tmp.append(i7)
											tmp.append(i8)
											tmp.append(i9)
											tmp.append(i10)
											retu.append(tmp[:N])
											tmp = []
	ans = 0

	for i in retu:
		#print(i)
		score = 0
		for vol in A:
			a,b,c,d = vol
			#print("{} {}".format(int(i[b-1]) - int(i[a-1]), c))
			if int(i[b-1]) - int(i[a-1]) == c:
				score += d

		if score > ans:
			ans = score

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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


def main(l, m):
    ret = 0
    if len(l) == N:
        for a, b, c, d in L:
            if l[b - 1] - l[a - 1] == c:
                ret += d
        return ret

    for i in range(m, M + 1):
        ret = max(ret, main(l + [i + 1], m))
    return ret


print(main([], 1))

Submission status: Wrong Answer

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

import itertools

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

    a_li = []

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

    ans = 0
    for l in itertools.combinations(range(1, m+1),n):
        point = 0
        for (a,b,c,d) in a_li:
            if l[b-1] - l[a-1] == c:
                point += d

        if point > ans:
            ans = point

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
ts = []
for _ in range(Q):
    ts.append(tuple(map(int, input().split())))
print(ts)

scores = []
for A in combinations_with_replacement(range(1, M + 1), N):
    score = 0
    for t in ts:
        a, b, c, d = t
        if A[b - 1] - A[a - 1] == c:
            score += d
    scores.append(score)

print(max(scores))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, product, permutations, combinations

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

com = combinations([i for i in range(1, M+1)], N)

ma = 0
scores = []
for i in com:
    score = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            score += j[3]
    if score > ma:
        ma = score
print(ma)

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]]
        A[b[i]]=c[i]+A[a[i]]
        if A[b[i]]>m:
            break
        
        #All Check
        tmp=0
        for j in range(q):
            if A[b[j]]-A[a[j]]==c[j]:
                tmp+=d[j]
        ans=max(ans,tmp)
    print(ans)
    
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, Q = [int(i) for i in input().split(" ")]
ans = 0
que = [i for i in range(1, N+1)]
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] = [int(j) for j in input().split(" ")]

while True:
    if len(que) == N:
        s=0
        for i in range(Q):
            if que[b[i]-1] - que[a[i]-1] == c[i]:
                s += d[i]
        ans = max(ans, s)
    n = que.pop()
    if n < M:
        for i in range(N):
            que.append(n+1)
            if len(que) == N:
                break
    if len(que) == 0:
        break

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

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))
'''
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())
l = [input().split() for i in range(Q)]
for i in range(Q):
    l[i][0] = int(l[i][0])
    l[i][1] = int(l[i][1])
    l[i][2] = int(l[i][2])
    l[i][3] = int(l[i][3])
A = [1]*N
max_point = -float('inf')
for i in range(N*M-1):
    point=0
    for j in range(Q):
        if(A[l[j][1]-1] - A[l[j][0]-1] == l[j][2]):
            point += l[j][3]
    if(max_point < point):
        max_point = point
    A[N-1] += 1    
    for j in range(N):
        if(A[N-1-j] > M):
          A[N-1-j] = 1
          A[N-2-j] += 1
print(max_point)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, Q = map(int, input().split())
l = []
for _ in range(Q):
    l.append(tuple(map(int, input().split())))
k = 1
for i in l:
  if i[2] == 0:
    k = max(k, i[1]-i[0])
c = list(itertools.combinations(list(range(1, M+1))*k, N))

max = 0
for i in c:
    i = list(i)
    i.sort()
    sum = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            sum += j[3]
    if max < sum:
        max = sum
        
print(max)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = map(int, input().split())
num_lists = [list(map(int, input().split())) for _ in range(q)]
A = list(range(1, m+1))
ans = 0
for a in itertools.product(A, repeat=n):
  point = 0
  for num_list in num_lists:
    if num_list[2] == a[num_list[1] - 1] - a[num_list[0] - 1]:
      point += num_list[3]
  ans = max(ans, point)
print(ans)

Submission status: Wrong Answer

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

A_full = np.arange(1,M+1)

l_tensu = [0]
for subset in itertools.combinations(A_full, N):
    tensu = 0

    A = np.sort(list(subset))
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
    
print(max(l_tensu))

Submission status: Wrong Answer

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

ans=0

def chousa(list,a,b,c,d):
    global q
    ans=0
    for i in range(q):
        if list[b[i]]-list[a[i]]==c[i]:
            ans+=d[i]
    return ans


rui=n+2
list=[1]*rui
list[rui-1]=m
u=0
while list[1]!=m:
    i=0

    while list[rui-1-i]==m :
        
        i=i+1
#最後から数えて銃じゃなくなったところ
    if rui-i!=1:
        list[rui-1-i]+=1

        ans=max(chousa(list,a,b,c,d),ans)


print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


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

a = [None] * Q
b = [None] * Q
c = [None] * Q
d = [None] * Q

for i in range(Q):
    num = list(map(int, input().split()))
    a[i], b[i], c[i], d[i] = num[0] - 1, num[1] - 1, num[2], num[3]

A = [i for i in range(1, M + 1)]
max_v = 0
for v in itertools.combinations(A, N):
    tmp_sum = 0
    for i in range(Q):
        if v[b[i]] - v[a[i]] == c[i]:
            tmp_sum += d[i]
    max_v = max(max_v, tmp_sum)

print(max_v)

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(Q):
  a = list(map(int,input().split()))
  List.append(a)
  
lis = [i for i in range(1,M+1)]
ans = 0

for team in itertools.product(lis, repeat=N):
  cnt = 0
  for i in range(Q):
    a = List[i][0]
    b = List[i][1]
    c = List[i][2]
    d = List[i][3]
    
    if team[b-1] - team[a-1] == c:
      cnt += d
  ans = max(ans ,cnt)  
  
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = map(int, input().split())
l = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    l.append([a-1, b-1, c, d])
ll = [i for i in range(1, 11)]
h = itertools.combinations_with_replacement(ll, n)
ans = 0
for v in h:
    vl = list(v)
    cnt = 0
    for i in range(q):
        ai, bi, ci, di = l[i]
        if vl[bi] - vl[ai] == ci:
            cnt += di
    ans = max(ans, cnt) 
print(ans)

Submission status: Wrong Answer

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

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

cond.sort()
#print(cond)
finalres = 0
dat = [1] * n
while dat[0] < m:
    dat[n - 1] += 1
    for i in range(n - 1, -1, -1):
        if dat[i] > m:
            dat[i] = dat[i - 1]
            dat[i - 1] += 1
        else:
            break
    ispass = False
    for i in range(n - 1, 0, -1):
        if dat[i] < dat[i - 1]:
            ispass = True
            break
    if ispass:
        continue

    #print("Try:", dat)

    can = True
    res = 0
    for i in range(q):
        a, b, c, d = cond[i]
        a, b = a-1, b-1
        if dat[b] - dat[a] == c:
            #print(" > match i{0} -i{1} == c gain {2}".format(b, a, d))
            res += d
    finalres = max(finalres, res)
print(finalres)

Submission status: Wrong Answer

Solution code:
import itertools

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

listn = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list_ex = list(itertools.combinations_with_replacement(listn, n))

ans = 0
for i in range(len(list_ex)):
    list_ex2 = list_ex[i]
    ans2 = 0
    for j in range(q):
        listi2 = listi[j]
        ai = listi2[0]-1
        bi = listi2[1]-1
        ci = listi2[2]
        if (list_ex2[bi] - list_ex2[ai] == ci):
            ans2 += listi2[3]
    if (ans < ans2):
        ans = ans2

print(ans)

Submission status: Wrong Answer

Solution code:
a=list(map(int,input().split()))
b=[]
c=[]
out=0
for i in range(a[2]):
  b.append(list(map(int,input().split())))
for i in range(a[0]):
  c.append(1)
for i in range(a[0]):
  for j in range(a[1]+1):
    d=0
    for k in range(a[2]):
      #print('i:'+str(i)+' j:'+str(j)+' k:'+str(k))
      #print(c)
      if c[b[k][1]-1]-c[b[k][0]-1]==b[k][2]:
        d+=b[k][3]
    if d>out:
      out=d
    if j+1>a[1]:
      c[a[0]-1-i]=j
    else:
      c[a[0]-1-i]=j+1
print(out)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

high_score = -1

for a in range(1,11):
    for b in range(a,11):
        for c in range(b,11):
            for d in range(c,11):
                for e in range(d,11):
                    for f in range(e,11):
                        for g in range(f,11):
                            for h in range(g,11):
                                for i in range(h,11):
                                    for j in range(i,11):
                                        score = 0
                                        A = [a,b,c,d,e,f,g,h,i,j]
                                        for li in l:
                                            if A[li[1]-1]-A[li[0]-1] == li[2]:
                                                score += li[3]
                                            if(high_score < score):
                                                high_score = score
print(high_score)