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:
#
# abc165 c
#
from itertools import combinations_with_replacement as cwr
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    global N, M
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for _ in range(Q)]

    T = []
    func([1], T)

    ans = 0
    for t in cwr(range(1, M+1), N):
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-a] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# abc165 c
#
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    global N, M
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for _ in range(Q)]

    T = []
    func([1], T)

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


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
#
# abc165 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    global N, M
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for _ in range(Q)]

    T = []
    func([1], T)

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


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(1000000)

n, m, q = map(int, input().split())
l = [list(map(int, input().split())) for i in range(q)]
aa = "1"
anss = []


def dfs(a):
    if len(a) == n + 1:
        ans = 0
        for i in range(q):
            if int(a[l[i][1]]) - int(a[l[i][0]]) == l[i][2]:
                ans += l[i][3]
        anss.append(ans)
        return

    a += a[-1]
    while int(a[-1]) <= m:
        dfs(a)
        a = list(a)
        a[-1] = str(int(a[-1]) + 1)
        "".join(a)


def main():
    dfs(aa)
    print(max(anss))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product

N, M, Q = map(int, input().split())
patterns = product(list(range(1, M+1)), repeat=N)
queries = [list(map(int, input().split())) for _ in range(Q)]

answer = 0
for pattern in patterns:
  point = 0
  for a, b, c, d in queries:
    if pattern[b-1] - pattern[a-1] == c:
      point += d
  answer = max(answer, point)
print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, M, Q = map(int, input().split())
patterns = combinations(list(range(1, M+1)), N)
queries = [list(map(int, input().split())) for _ in range(Q)]

answer = 0
for pattern in patterns:
  point = 0
  for a, b, c, d in queries:
    if pattern[b-1] - pattern[a-1] == c:
      point += d
  answer = max(answer, point)
print(answer)

Submission status: Wrong Answer

Solution code:
def dfs(lst):
    global ans
    if len(lst) > n:
        return
    lowest = 0
    if lst != []:
        lowest = lst[-1]
    for i in range(lowest, m+1):
        lst.append(i)
        dfs(lst)
        lst.pop()
    if len(lst) == n:
        cnt = 0
        for i in range(q):
            a, b, c, d = ab[i]
            if lst[b-1] - lst[a-1] == c:
                cnt += d
        ans = max(cnt, ans)

n,m,q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
dfs([])

print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(lst):
    global ans
    if len(lst) > n:
        return
    lowest = 0
    if lst != []:
        lowest = lst[-1]
    for i in range(lowest+1, m+1):
        lst.append(i)
        dfs(lst)
        lst.pop()
    if len(lst) == n:
        cnt = 0
        for i in range(q):
            a, b, c, d = ab[i]
            if lst[b-1] - lst[a-1] == c:
                cnt += d
        ans = max(cnt, ans)

n,m,q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
dfs([])

print(ans)

Submission status: Wrong Answer

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


big_lis = []


def dfs(string, n, m):
    if n == (N - 1):
        for i in range(m, M + 1):
            big_lis.append(string + [i])
    else:
        for i in range(m, M + 1):
            dfs(string + [i], n + 1, i)


dfs([], 0, 0)

MAX_A = 0
for small_lis in big_lis:
    D = 0
    for j in range(Q):
        if small_lis[int(lis[j][1]) - 1] - small_lis[int(lis[j][0]) - 1] == int(lis[j][2]):
            D += int(lis[j][3])
    MAX_A = max(MAX_A, D)
print(MAX_A)

Submission status: Wrong Answer

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


big_lis = []


def dfs(string, n, m):
    if n == (N - 1):
        for i in range(m, M + 1):
            big_lis.append(string + str(i))
    else:
        for i in range(m, M + 1):
            dfs(string + str(i), n + 1, i)


dfs('', 0, 0)

MAX_A = 0
for small_lis in big_lis:
    D = 0
    for j in range(Q):
        if int(small_lis[int(lis[j][1]) - 1]) - int(small_lis[int(lis[j][0]) - 1]) == int(lis[j][2]):
            D += int(int(lis[j][3]))
    MAX_A = max(MAX_A, D)
print(MAX_A)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


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 main():
    N, M, Q = MI()
    targets = [[] for i in range(Q)]
    for i in range(Q):
        target = LI()
        targets[i] = target
    ans = 0
    for i in range(1, 2**(M+N-1)):
        i_str = format(i, f"0{M+N-1}b")
        A = []
        tmp = 1
        for k in range(len(i_str)):
            if i_str[k] == "1":
                tmp += 1
            else:
                A.append(tmp)
        if len(A) != N:
            continue
        score = 0
        for query in targets:
            a, b, c, d = query
            if A[b-1] - A[a-1] == c:
                score += d
        ans = max(ans, score)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
N, M, Q = map(int, input().split())
Q = [list(map(int,input().split())) for _ in range(Q)]
ans = 0
A = []
def dfs():
    global A
    if len(A) == N:
        return
    global ans
    if len(A) == 0:
        start = 0
    else:
        start = A[-1]
    for i in range(start, M + 1):
        A.append(i)
        dfs()
        if len(A) != N:
            A.pop()
            continue
        tmp_ans = 0
        for a, b, c, d in Q:
            if A[b - 1] - A[a - 1] == c:
                tmp_ans += d
        ans = max(ans, tmp_ans)
        A.pop()
dfs()
print(ans)

Submission status: Wrong Answer

Solution code:
def f(n, m, arrs=[], arr=[]):
    if len(arr) == n:
        arrs.append(arr)
    else:
        if len(arr) == 0:
            for i in range(m + 1):
                f(n, m, arrs, arr + [i])
        else:
            for i in range(arr[-1], m + 1):
                f(n, m, arrs, arr + [i])
    return arrs


n, m, q = map(int, input().split())
memo = {}
for _ in range(q):
    a, b, c, d = map(int, input().split())
    if (a, b) not in memo.keys():
        memo[(a, b)] = [c, d]
    else:
        memo[(a, b)][1] += d
#print(memo)
ans = 0
for ball in f(n, m):
    a = 0
    for q in memo.keys():
        if ball[q[1] - 1] - ball[q[0] - 1] == memo[q][0]:
            a += memo[q][1]
    ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

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

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

def calc(B, n):
  ans = 0
  #not enough length
  if len(B) < N:
    for i in range(n, M + 1):
      ans = max(ans, calc(B + [i], i))
  #enough length
  else:
    print("B:", B)
    for j in range(Q):
      if B[A[j][1]-1] - B[A[j][0]-1] == A[j][2]:
        ans += A[j][3]
    print("ans:", ans)
  return ans



print(calc([], 1))

Submission status: Wrong Answer

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

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

def calc(B, n):
  ans = 0
  if len(B) < N:
    for i in range(n, M + 1):
      ans = max(ans, calc(B + [i], i))
      return ans
  else:
    for j in range(Q):
      if B[A[j][1]-1] - B[A[j][0]-1] == A[j][2]:
        ans += A[j][3]
    return ans


print(calc([], 1))

Submission status: Wrong Answer

Solution code:
def backtrack(nums, N, cur_state, result):
    if len(cur_state) == N:
        result.append(cur_state[:])
    else:
        for i in range(len(nums)):
            cur_state.append(nums[i])
            backtrack(nums[i:], N, cur_state, result)
            cur_state.pop()

def solve():
    N,M,Q = [int(i) for i in input().split()]
    quads = []
    for i in range(Q):
        quads.append([int(i) for i in input().split()])
    candidates = []
    backtrack(list(range(1, 11)), N, [], candidates)

    ans = 0
    for candidate in candidates:
        score = 0
        for a,b,c,d in quads:
            if candidate[b-1] - candidate[a-1] == c:
                score += d
        ans = max(score, ans)
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#C - Many Requirements
#再帰関数(n重のfor文)
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
max_score = 0
def dfs(A):
    global max_score
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 0
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
dfs([])
print(max_score)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
def dfs(A):
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    max_score = 0 
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 0
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
print(dfs([]))

Submission status: Wrong Answer

Solution code:
#C - Many Requirements
#再帰関数(n重のfor文)
N,M,Q = map(int,input().split())
abcd = [(0,0,0,0)]*Q
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
max_score = 0
def dfs(A):
    global max_score
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 0
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
dfs([])
print(max_score)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
abcd = [(0,0,0,0)]*Q
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
max_score = 0
def dfs(A):
    global max_score
    if len(A) == N:
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 1
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score
dfs([])
print(max_score)

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
def dfs(A):
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    max_score = 0 
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 1
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
print(dfs([]))

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
max_score = 0
def dfs(A):
    global max_score
    if len(A) == N:
        #処理
        score = 0
        for ai,bi,ci,di in abcd:
            if A[bi-1] -A[ai-1] == ci:
                score += di
        return score
    #一つ前の値を保持
    if len(A) > 1:
        prev_last = A[-1]
    else:
        prev_last = 1
    #1つ前の値より大きい値の範囲
    for i in range(prev_last,M+1):
        A.append(i)
        max_score = max(max_score,dfs(A))
        A.pop()
    return max_score#ループの途中のdfs (len(A) != N のとき) に値を返す
dfs([])
print(max_score)

Submission status: Wrong Answer

Solution code:
import sys
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
ans = 0
done = set()
todo = [(i,) for i in range(1, M)]
while todo:
    A = todo.pop()
    done.add(A)
    if len(A) == N:
        total = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                total += d
        ans = max(ans, total)
        continue
    for i in range(A[-1], M + 1):
        nA = A + (i,)
        if not nA in done:
            todo.append(nA)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
def main():
    n, m, q = map(int, input().split())
    matrix = []
    for _ in range(q):
        row = list(map(int, input().split()))
        matrix.append(row)
    # print(matrix)
    A = list(range(1, m))
    ans = 0
    for tmp_A in itertools.combinations_with_replacement(A, n):
        tmp_A = sorted(list(tmp_A))
        tmp_ans = 0
        for row in matrix:
            # print("row", row)
            # print("tmp_A", tmp_A)
            tmp = tmp_A[row[1] - 1] - tmp_A[row[0]- 1]
            if row[2] == tmp:
                tmp_ans += row[3]
        if tmp_ans >= ans:
            ans = tmp_ans
            
    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
def main():
    n, m, q = map(int, input().split())
    matrix = []
    for _ in range(q):
        row = list(map(int, input().split()))
        matrix.append(row)
    # print(matrix)
    A = list(range(1, 11))
    ans = 0
    for tmp_A in itertools.combinations_with_replacement(A, n):
        tmp_A = sorted(list(tmp_A))
        tmp_ans = 0
        for row in matrix:
            # print("row", row)
            # print("tmp_A", tmp_A)
            tmp = tmp_A[row[1] - 1] - tmp_A[row[0]- 1]
            if row[2] == tmp:
                tmp_ans += row[3]
        if tmp_ans >= ans:
            ans = tmp_ans
            
    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i in range(1<<(2*n)):
  a=[1]
  for j in range(2*n):
    if (i>>j)&1:a[-1]+=1
    else:a+=[a[-1]]
    if a[-1]>m:
      flag=0
      break
    if len(a)>n:
      flag=1
      break
  else:flag=1
  if flag==0 or len(a)<n:continue
  cnt=0
  for s,t,u,v in e:
    if a[t-1]-a[s-1]==u:cnt+=v
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i in range(1<<(2*n-1)):
  a=[1]
  for j in range(2*n-1):
    if (i>>j)&1:a[-1]+=1
    else:a+=[a[-1]]
    if a[-1]>m:
      flag=0
      break
    if len(a)>n:
      flag=1
      break
  else:flag=1
  if flag==0 or len(a)<n:continue
  cnt=0
  for s,t,u,v in e:
    if a[t-1]-a[s-1]==u:cnt+=v
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M,Q = map(int,input().split())
T=[tuple(map(int,input().split())) for _ in range(Q)]
ans=0
for v in itertools.combinations(range(1,M+1),N):
  tmp=0
  for a,b,c,d in T:
    if v[b-1]-v[a-1]==c:
      tmp+=d
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M,Q = map(int,input().split())
T=[tuple(map(int,input().split())) for _ in range(Q)]
ans=0
for v in itertools.permutations(range(1,M+1),N):
  tmp=0
  for a,b,c,d in T:
    if v[b-1]-v[a-1]==c:
      tmp+=d
  ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

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


a = [1]*n
def next_a(a):
    if a[-1] != 10:
        a[-1] += 1
    else:
        d = n-1
        while d > 0 and a[d] == 10:
            d-=1
        if d < 0:
            return a
        a[d] += 1
        next = a[d]
        for i in range(d,n):
            a[i] = next
max = -1
a[-1] = 0
while sum(a) != n*10:
    next_a(a)
    test = 0
    for i in range(q):
        if a[abcd_list[i][1]-1] - a[abcd_list[i][0]-1] == abcd_list[i][2]:
            test += abcd_list[i][3] 
    if test > max:
        max = test

print(max)

Submission status: Wrong Answer

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

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


a = [1]*n

def next_a(a):
    if a[-1] != 10:
        a[-1] += 1
    else:
        d = n-1
        while d > 0 and a[d] == 10:
            d-=1
        if d < 0:
            return a
        a[d] += 1
        next = a[d]
        for i in range(d,n):
            a[i] = next
max = -1
a[-1] = 0
while sum(a) != n*10:
    next_a(a)
    test = 0
    for i in range(q):
        if a[abcd_list[i][1]-1] - a[abcd_list[i][0]-1] == abcd_list[i][2]:
            test += abcd_list[i][3] 
        if test > max:
            max = test

print(max)

Submission status: Wrong Answer

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

def score(A):
    score =0
    for ai, bi, ci, di in zip(a,b,c,d):
        if A[bi] - A[ai] == ci:
            score += di
    return di

def dfs(A):
    #print(A)
    if len(A)==n:
        return score(A)
    res = 0
    last_term = A[-1] if len(A) >0 else 0
    for i in range(last_term, m):
        A.append(i)
        res = max(res, dfs(A))
        A.pop()
    
    return res

print(dfs([]))

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
    a[i] -= 1  #a,bを0オリジンにそろえる
    b[i] -= 1  

def score(A):
    score = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            score += ci
    return score

def dfs(A):
    if len(A) == N:
        return score(A)
    res = 0
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        res = max(res, dfs(A))
        A.pop()
    return res

print(dfs([]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

for A in canditates:
    _temp = 0
    for a, b, c, d in abcd:
        try:
            if A[b - 1] - A[a - 1] == c:
                _temp += d
        except BaseException:
            pass
    ans = max(ans, _temp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], m)

try:
    for A in canditates:
        _temp = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                _temp += d
        ans = max(ans, _temp)
except BaseException:
    pass

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, m, q = map(int, input().split())
    m = map(int, read().split())
    mm = zip(m, m, m, m)
    dp = [[0] * 200 for _ in range(n)]
    for a, b, c, d in mm:
        a -= 1
        b -= 1
        for i1 in range(100):
            dp[b][i1+c] += dp[a][i1] + d
    r = max(dp[n-1][:n+1])
    print(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

temp = list(combinations([i for i in range(1,m+1)],n))


ans = 0

for a_temp in temp:
    ans_temp = 0
    for i in range(q):
        if a_temp[a[i][1]-1] - a_temp[a[i][0]-1] == a[i][2]:
            ans_temp += a[i][3]
    if ans < ans_temp:
        ans = ans_temp
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

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

    A = [1 for _ in [0] * N]
    end = N - 1
    ans = 0
    while A[-1] < M + 1:
        score = 0
        for i in range(Q):
            lst_now = lst[i]
            if A[lst_now[1] - 1] - A[lst_now[0] - 1] == lst_now[2]:
                score += lst_now[3]
        ans = max(ans, score)
        if A[end] >= M:
            end -= 1
        A[end] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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(6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp = 0
                    arrs = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b] - arrs[a] == c:
                        tmp += d
                    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for x in range(q)]
ans = 0

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(6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp = 0
                    arrs = [0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b] - arrs[a] == c:
                        tmp += d
                    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n,m,q =map(int, input().split())
qs = []
ans = 0
for i in range(q):
    arr= list(map(int, input().split()))
    qs.append(arr)
    
def calc(x):
    global ans
    tmp = 0
    for i in range(q):
        if(x[qs[i][1]-1]-x[qs[i][0]-1]==qs[i][2]):
            tmp+=qs[i][3]
    ans = max(ans, tmp)

def dfs(x):
    if(len(x)==n):
        calc(x)
    else:
        for i in range(x[-1], m+1):
            if(i!= x[-1]):
                x.append(i)
                dfs(x)
                x.pop()
dfs([1])
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
a_list = []
b_list = []
c_list = []
d_list = []
for _ 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)

import itertools

ans = 0
h_list = [i+1 for i in range(m)]
for A in itertools.combinations(h_list, n):
    max_d = 0
    for a, b, c, d in zip(a_list, b_list, c_list, d_list):
        if A[b-1]-A[a-1] == c:
            max_d += d
    ans = max(ans, max_d)

print(ans)

Submission status: Wrong Answer

Solution code:

def score(Q,A,a,b,c,d):
    ans = 0
    for i in range(Q):
        if A[b[i]] - A[a[i]] == c[i]:
            ans += d[i]

    return ans


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


mx = 0
A = [1]*(N+1)
for i in range(M**N):
    tmp = i
    for j in range(N,0,-1):
        A[j] = tmp % M + 1
        tmp //= M

    scr = score(Q, A, a, b, c, d)
    # print("A=", A, "  score=", scr)
    if mx < scr:
        mx = scr

print(mx)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
ans_list = []
for num in range(2 ** m):
    tmp = [0]
    for i in range(m):
        if num & (1 << i):
            tmp.append(i+1)
    if len(tmp) == n+1:
        ans_list.append(tmp)
        #print(tmp)
#print(len(ans_list))
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[i] = a_i
    b[i] = b_i
    c[i] = c_i
    d[i] = d_i

ans = 0
for j in range(len(ans_list)):
    sum_tmp = 0
    for i in range(q):
        if ans_list[j][b[i]] - ans_list[j][a[i]] == c[i]:
            sum_tmp += d[i]
    #print(ans_list[j],sum_tmp)
    ans = max(ans,sum_tmp)

print(ans)