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:
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)]*M, 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:
n, m, q = map(int,input().split())
abcd = []
for _ in range(q):
    abcd.append(list(map(int,input().split())))

a_l = [1] * n
ans = 0
while True:
    if a_l == [m]*n:
        break
    ans_tmp = 0
    for a, b, c, d in abcd:
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = min(a_l[-(i+1)] + 1, m)
            continue
        else:
            break

print(ans)

Submission status: Wrong Answer

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

p_max = 0
point =0
A = [1]*n
E = [m]*n

while A != E :

    #得点計算
    for j in range(q):
        if A[List[j][1]-1] - A[List[j][0]-1] == List[j][2]:
            point += List[j][3]


    #最大値の更新
    if p_max < point:
        p_max = point


    #Aの更新
    for i in reversed(range(0,n)):
        if A[i] < m:
            A[i] = A[i] + 1
            if i !=n-1:
                for k in range(i+1,n):
                    A[k] = A[i]
            break

print(p_max)

Submission status: Wrong Answer

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

p_max = 0
point =0
A = [1]*n
E = [m]*n

while A != E :

    #得点計算
    for j in range(q):
        if A[List[j][1]-1] - A[List[j][0]-1] == List[j][2]:
            point += List[j][3]
    #print(j,point)
    print(point)
    #最大値の更新
    if p_max < point:
        p_max = point


    #Aの更新
    for i in reversed(range(0,n)):
        if A[i] < m:
            A[i] = A[i] + 1
            if i !=n-1:
                for k in range(i+1,n):
                    A[k] = A[i]
            break

print(p_max)

Submission status: Wrong Answer

Solution code:
from itertools import product
def score_check(A,L):
    point = 0
    for a, b, c, score in L:
        temp = A[b - 1] - A[a - 1]
        if temp == c:point += score

    return point

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

num = 0
for i in product(list(range(1, m + 1)), repeat = n):
    #print(i)
    temp = score_check(i, l)
    if num < temp:num = temp
print(num)

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 = [1] * 10

def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      t += d[i]
  if ans < t:
    return t
  else:
    return ans

ans = 0
for i1 in range(1, m):
  A[1] = i1
  if n >= 3:
    for i2 in range(i1, m):
      A[2] = i2
      if n >= 4:
        for i3 in range(i2, m):
          A[3] = i3
          if n >= 5:
            for i4 in range(i3, m):
              A[4] = i4
              if n >= 6:
                for i5 in range(i4, m):
                  A[5] = i5
                  if n >= 7:
                    for i6 in range(i5, m):
                      A[6] = i6
                      if n >= 8:
                        for i7 in range(i6, m):
                          A[7] = i7
                          if n >= 9:
                            for i8 in range(i7, m):
                              A[8] = i8
                              if n >= 10:
                                for i9 in range(i8, m):
                                  A[9] = i9
                                  ans = check(A, ans)
                              else:
                                ans = check(A, ans)
                          else:
                            ans = check(A, ans)
                      else:
                        ans = check(A, ans)
                  else:
                    ans = check(A, ans)
              else:
                ans = check(A, ans)
          else:
            ans = check(A, ans)
      else:
        ans = check(A, ans)
  else:
    ans = check(A, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_score(arr):
        current_score = 0
        for i, j, dist, score in L:
            if arr[j] - arr[i] == dist:
                current_score += score
        return current_score
    
    
    n, m, q = mi()
    L = []
    for _ in range(q):
        a, b, c, d = mi()
        L.append([a-1, b-1, c, d])
    
    ans = 0
    number_array = []
    for i_0 in range(10):
        for i_1 in range(i_0, 10):
            for i_2 in range(i_1, 10):
                for i_3 in range(i_2, 10):
                    for i_4 in range(i_3, 10):
                        for i_5 in range(i_4, 10):
                            for i_6 in range(i_5, 10):
                                for i_7 in range(i_6, 10):
                                    for i_8 in range(i_7, 10):
                                        for i_9 in range(i_8, 10):
                                            number_array = [i_0, i_1, i_2, i_3, i_4, i_5, i_6, i_7, i_8, i_9]
                                            ans = max(ans, calc_score(number_array))
    print(ans)
                         


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

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

    Alist = itertools.combinations_with_replacement(range(1,m+1),n)

    ans = 0
    print(a,b,c,d)
    for A in Alist:
        cnt = 0
        for i in range(1,q+1):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                cnt += d[i]
        ans = max(ans,cnt)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
q_list = []
final_score = 0
N, M, Q = map(int, input().split())
for i in range(Q):
    q_list.append(list(map(int, input().split())))
K = [0] * 10
for i1 in range(1, 11):
    K[0] = i1
    for i2 in range(i1, 11):
        K[1] = i2
        for i3 in range(i2, 11):
            K[2] = i3
            for i4 in range(i3, 11):
                K[3] = i4
                for i5 in range(i4, 11):
                    K[4] = i5
                    for i6 in range(i5, 11):
                        K[5] = i6
                        for i7 in range(i6, 11):
                            K[6] = i7
                            for i8 in range(i7, 11):
                                K[7] = i8
                                for i9 in range(i8, 11):
                                    K[8] = i9
                                    for i10 in range(i9, 11):
                                        K[9] = i10
                                        score = 0
                                        for q in q_list:
                                            if K[q[1]-1] - K[q[0]-1] == q[2]:
                                                score += q[3]
                                            final_score = max([final_score, score])
print(final_score)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

l = []
def dfs(s, n):
    if n == N:
        l.append(s)
        return
    for i in range(int(s[-1]),M+1):
        dfs(s+str(i), n+1)

for i in range(M+1):
    dfs(str(i), 1)
ans = 0
for i in l:
    ans = max(ans, calc(list(map(int,i))))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,q=l_in()

abcd=[]
for _ in range(q):
    abcd.append(l_in())

s = []

def check(s):
    return sum(d for a,b,c,d in abcd if s[b-1] - s[a-1] == c)

def search(s, current):
    tmp = 0
    for d in range(current, m+1):
        s.append(d)
        if len(s) == n:
            tmp = max(tmp, check(s))
        else:
            tmp = max(tmp, search(s, d))
        s.pop()
        
    return tmp

print(search(s,0))

Submission status: Wrong Answer

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

a_l = [1] * n
ans = 0
while True:
    if a_l == [m]*n:
        break
    ans_tmp = 0
    for i in range(q):
        if a_l[abcd[i][1]-1] - a_l[abcd[i][0]-1] == abcd[i][2]:
            ans_tmp += abcd[i][3]
    ans = max(ans,ans_tmp)
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break

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

a=[]
for i in range(n-1):
  a.append(1)
a.append(0)
current=0
b=[]
for i in range(n):
  b.append(m)
while a!=b:
  i=n-1
  while a[i]==m:
    i=i-1
  a[i]+=1
  for j in range(i+1,n):
      a[j]=1
  d=0
  for j in range(q):
    if (a[l[j][1]-1]-a[l[j][0]-1])==l[j][2]:
      d+=l[j][3]
  if d>current:
    current=d

print(current)

Submission status: Wrong Answer

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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == 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]-1] - A[lis[j][0]-1] == lis[j][2]:
                                                    P += lis[j][3]
                                            if P > G:
                                                G = P
    print(G)

Submission status: Wrong Answer

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

a_l = [1] * n
ans = 0
while True:
    if a_l == [m]*n:
        break
    ans_tmp = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    vecs = [[1] for _ in range(N)]
    for a, b, c, d in abcd:
        for aa in vecs[a-1]:
            if aa + c not in vecs[b-1] and aa + c <= M:
                vecs[b-1].append(aa+c)

    def makelist(n, a,lists):
        if n == N:
            return lists.append(a)
        for v in vecs[n]:
            makelist(n+1, a+[v], lists)
        return True
    lists = []
    makelist(0, [], lists)

    ans = 0
    for A in lists:
        ans_ = 0
        for q in range(Q):
            a, b, c, d = abcd[q]
            if A[b-1] - A[a-1] == c:
                ans_ += d
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from itertools import combinations_with_replacement

n, m, q = na()
abcd = nan(q)

ans = 0
for p in combinations_with_replacement(range(1, 11), 10):
    t = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        a -= 1
        b -= 1
        if p[b] - p[a] == c:
            t += d
    ans = max(ans, t)

print(ans)

Submission status: Wrong Answer

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

for i in range(10**(N-1),10**(N)):
    answer = 0
    for j in range(Q):
        if (i//(10**(N-L[j][0])))%10-(i//(10**(N-L[j][1])))%10==L[j][2]:
            answer += L[j][3]
        if max_answer< answer:
            max_answer= answer
print(max_answer)

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

a_l = [1] * n
ans = 0
while True:
    if a_l == [m]*n:
        break
    ans_tmp = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#20C10のcombinatrics全探索？
#本番でCでこれ見たら凍るw
n,m,q=map(int, input().split( ))
qs=tuple(tuple(map(int, input().split( ))) for _ in range(q))
import itertools
ans=0
for comb in itertools.combinations(range(1,n+m+1),n):
    tmp=0
    comb2=[comb[i]-i for i in range(n)]
    for ai,bi,ci,di in qs:
        if comb2[bi-1]-comb2[ai-1]==ci:
            tmp+=di 
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
a=[0 for i in range(Q)]
b=[0 for i in range(Q)]
c=[0 for i in range(Q)]
d=[0 for i in range(Q)]
A=[0 for i in range(N)]
def swap(a,b,c):
    kari=a[b]
    a[b]=a[c]
    a[c]=kari
    return a
for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int, input().split())
for i in range(0,N):
    if(Q==1):
        break
    for j in range(1,N-i):
        if d[j]>d[j-1]:
            d=swap(d,j,j-1)
            a=swap(a,j,j-1)
            b=swap(b,j,j-1)
            c=swap(c,j,j-1)
sum=0
recode={}
for i in range(0,Q):
    if a[i] in recode.keys() and b[i] in recode.keys():
        continue
    else:
        recode[a[i]]=1
        recode[b[i]]=1
        sum+=d[i]
print(sum)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,m,q=l_in()

abcd=[]
for _ in range(q):
    abcd.append(l_in())

s = []

def check(s):
    return sum(d for a,b,c,d in abcd if s[b-1] - s[a-1] == c)

def search(s, current):
    tmp = 0
    for d in range(current, m+1):
        s.append(d)
        if len(s) == n:
            tmp = max(tmp, check(s))
        else:
            tmp = max(tmp, search(s, d))
        s.pop()

    return tmp


print(search(s,0))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import copy
import sys

rl = sys.stdin.readline

n,m,q=map(int,rl().split())
x=[list(map(int,rl().split())) for i in range(q)]
#x.sort(key=lambda x:x[3],reverse=True)

def calc(lst):
  sum=0
  #print(lst)
  for a,b,c,d in x:
    if(lst[b]-lst[a]==c):
      sum+=d
      #print(a,b,c,d,sum)
  return sum
      
def dfs(n,lst,i):
  ans=0
  lst.append(i)
  if(n==0):
    ans=calc(lst)
  else:
    for j in range(i,m+1):
      tmp=copy.copy(lst)
      ans=max(ans,dfs(n-1,tmp,j))
  return ans


print(dfs(n+1,[],0))

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

a_l = [1] * n
ans = 0
while True:
    if a_l == [m]*n:
        break
    ans_tmp = 0
    for i in range(q):
        a = abcd[i][0]
        b = abcd[i][1]
        c = abcd[i][2]
        d = abcd[i][3]
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
li=[list(map(int,input().split()))for _ in range(q)]
ans = 0
def dfs(i,A):
    global ans 
    if i == m:
        return
    tmp = 0
    for a,b,c,d in li:
        if A[b-1] - A[a-1] == c:
            tmp += d 
    ans = max(ans,tmp)
    tmp = A[:]
    for j in range(n):
        tmp = A[:]
        for k in range(1,j+2):
            tmp[-k] += 1
        dfs(i+1,tmp)
dfs(1,[1]*n)
print(ans)

Submission status: Wrong Answer

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

p_max = 0
point =0
A = [1]*n
E = [m]*n

while A != E :

    #得点計算
    for j in range(q):
        if A[List[j][1]-1] - A[List[j][0]-1] == List[j][2]:
            point += List[j][3]
  #      print(j,point)

    #最大値の更新
    if p_max < point:
        p_max = point
    point = 0

    #Aの更新
    for i in reversed(range(0,n)):
        if A[i] < m:
            A[i] = A[i] + 1
            if i !=n-1:
                for k in range(i+1,n):
                    A[k] = A[i]
            break
#        elif A[i-1] == m:
#            A[i] = m
#        else:
#            A[i] = A[i-1] + 1 
#    print(A)
print(p_max)

Submission status: Wrong Answer

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N,M,Q = map(int, input().split())		# 5 7 2

X=[]
for i in range(Q):
	a,b,c,d = map(int, input().split())		# 5 7 2
	a-=1
	b-=1
	X.append([a,b,c,d])



def score(X,A):
	iReturn=0
	for q in range(Q):
		a = X[q][0]
		b = X[q][1]
		c = X[q][2]
		d = X[q][3]
		
		if A[b]-A[a]==c: iReturn+=d
	
	return iReturn

ans=0
for i0 in range(0,10):
	for i1 in range(i0,10):
		for i2 in range(i1,10):
			for i3 in range(i2,10):
				for i4 in range(i3,10):
					for i5 in range(i4,10):
						for i6 in range(i5,10):
							for i7 in range(i6,10):
								for i8 in range(i7,10):
									for i9 in range(i8,10):
										A=[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9]
										ans = max(ans,score(X,A))

print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
A=[list(map(int,input().split())) for i in range(Q)]
ans=0
def make(N,ans):
  def saiki(i,j,_,ans):
    if i==N-1:
      for k in range(j,11):
        _[i]=k
        _ans=0
        for a in A:
          if _[a[1]-1]-_[a[0]-1]==a[2]:
            _ans+=a[3]
        ans=max(ans,_ans)
        #print(_)
      return ans
    for k in range(j,11):
      _[i]=k
      ans=saiki(i+1,k,_,ans)
    return ans

  _=[1]*N
  i=0
  for j in range(1,11):
    ans=saiki(i,j,_,ans)
  return ans
ans=make(N,-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as cmb

N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
s = 0

for _ in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

for A in cmb(range(1,M+1),N):
    _s = 0
    for q in range(Q):
        if A[b[q]-1] - A[a[q]-1] == c[q]:
            _s += d[q]
    
    s = max(s,_s)

print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # import sysすること！再帰の深さ制限を緩くする
n, m, q = list(map(int, input().split()))
data = []
for i in range(q):
    a, b, c, d = list(map(int, input().split()))
    data.append([a-1, b-1, c, d])


def dfs(t):
    if len(t) == n:
        score = 0
        for a, b, c, d in data:
            if t[b] - t[a] == c:
                score += d
        global ans
        ans = max(ans, score)
        return

    if len(t) == 0:
        s = 0
    else:
        s = t[-1]

    for j in range(s, m+1):
        tmp = t[:]
        dfs(tmp+[j])


ans = 0
dfs([])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations_with_replacement
def main():
    N, M, Q = map(int, input().split())
    q_list = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        q_list.append((a, b, c, d))
    A = combinations_with_replacement("0123456789", N)
    ans = 0
    for Ai in A:
        v = 0
        Ai = list(map(int, Ai))
        for a, b, c, d in q_list:
            if Ai[b-1]-Ai[a-1] == c:v += d
        ans = max(ans, v)
    print(ans)
if __name__ == "__main__":
    main()