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 combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    qlist = []
    for _ in range(q):
        qlist.append(tuple(map(int, input().split())))

    nums = [i for i in range(0, m + 1)]
    alist = tuple(combinations_with_replacement(nums, n))

    r = 0
    for al in alist:
        tr = 0
        for eq in qlist:
            eq0 = eq[0] - 1
            eq1 = eq[1] - 1
            eq2 = eq[2]
            eq3 = eq[3]
            if al[eq1] - al[eq0] == eq2:
                tr += eq3
        r = max(r, tr)

    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M,Q = map(int, input().split())
inf = []
for i in range(Q):
    a,b,c,d = map(int, input().split())
    inf.append([a,b,c,d])
from collections import deque

inf = sorted(inf, key=lambda x:x[3])
inf = deque(inf)
used = [False]*(N+1)
ans = 0

"""貪欲方？"""
while len(inf) > 0:
    in1 = inf.pop()
    if not (used[in1[0]] == True and used[in1[1]] ==True):
        ans += in1[3]
        used[in1[0]] = True
        used[in1[1]] = True

print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(A, M, i):
  if i < 0:
    return
  A[i] += 1
  if A[i] > M:
    dfs(A, M, i-1)
    if i-1 >= 0:
      A[i] = A[i-1]

N,M,Q=map(int, input().split())
a,b,c,d = [], [], [], []
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)

A = [1]*N
ans = 0

for _ in range(1000):
  dsum = 0
  for i in range(Q):
    ai,bi,ci,di = a[i], b[i], c[i], d[i]
    if A[bi-1]-A[ai-1] == ci:
      dsum += di
  ans = max(ans, dsum)

  #終了条件
  if A[0]==M:
    break

  #終了しない場合は次の数字
  dfs(A, M, N-1)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
ans = 0
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):
                    lst = [0,a,b,c,d,e,f,g,h,i,j]
                    print(lst)
                    s = 0
                    for l in range(q):
                      s += abcd[l][3]*(lst[abcd[l][1]]-lst[abcd[l][0]]==abcd[l][2])
                    ans = max(ans, s)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def ls_incr(arg_ls, max_n):
	temp_min, temp_max = arg_ls[0], arg_ls[-1]
	if temp_min == temp_max:
		if temp_max < max_n:
			ls_len = len(arg_ls)
			arg_ls = [1 for _ in range(ls_len)]
			arg_ls[-1] = (temp_max + 1)
			return arg_ls
		else:
			return False
	rv_ls = arg_ls[::-1]
	for i,n in enumerate(rv_ls):
		if n >= temp_max: continue
		rv_ls[i] += 1
		return rv_ls[::-1]

# 入力取得
inp_ls = input().split(" ")
n,m,q = [int(e) for e in inp_ls[:3]]

nums_ls = []
for i in range(q):
	one_inp_ls = input().split(" ")
	a,b,c,d = [int(e) for e in one_inp_ls[:4]]
	nums_ls.append([a,b,c,d])

a_ls = [1 for i in range(n)]
max_sum = 0
while True:
	sum_val = 0
	for a,b,c,d in nums_ls:
		if c == (a_ls[b-1]-a_ls[a-1]):
			sum_val += d
	if max_sum < sum_val: max_sum = sum_val
	a_ls = ls_incr(a_ls, m)
	if a_ls is False: break

print(max_sum)

Submission status: Wrong Answer

Solution code:
import itertools

N,M,Q  = map(int,input().split())
#N長さ
#M数列のmax
#Q組み
score=[]
for i in range(Q):
    score.append(list(map(int,input().split())))
    
num =[i for i in range(1,N+M+1)]
br =itertools.combinations(num,N)
maxcount = 0
for i in br:
    count = 0
    for j in range(Q):
        if i[score[j][1]-1] -i[score[j][0]-1] == score[j][2]:
            count += score[j][3]
    maxcount = max(count,maxcount)
print(maxcount)

Submission status: Wrong Answer

Solution code:
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

N, M, Q = map(int,input().split())
S = [[int(x) for x in input().split()]for i in range(Q)]
Max = 0
for i in range(M**(N-1),M**N):
  count = 0
  a = Base_10_to_n(i, M)
  A = [int(k)+1 for k in list(a)]
  A.sort()
  for j in range(Q):
    if A[S[j][1]-1]-A[S[j][0]-1] == S[j][2]:
      count += S[j][3]
  if count > Max:
    Max = count
print(Max)

Submission status: Wrong Answer

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

import sys
from collections import namedtuple

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

Q = namedtuple("Q", ("a", "b", "c", "d"))

def enumerate_a(n):
    def _enumuerate_a(begin, depth):
        if depth == n:
            yield []
            return
        for i in range(begin, 11):
            yield from ([i] + a for a in _enumuerate_a(i, depth + 1))
    yield from _enumuerate_a(1, 0)

def main():
    n, m, q = read_list(int)
    qs = []
    for i in range(q):
        qi = Q(*read_list(int))
        qs.append(qi)
    
    max_dsum = 0
    for a in enumerate_a(n):
        dsum = 0
        for q in qs:
            if a[q.b - 1] - a[q.a - 1] == q.c:
                dsum += q.d
        max_dsum = max(dsum, max_dsum)
    print(max_dsum)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
from collections import namedtuple

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

Q = namedtuple("Q", ("a", "b", "c", "d"))

def enumerate_a(n):
    def _enumuerate_a(begin, depth):
        if depth == n:
            yield []
            return
        for i in range(begin, 10):
            yield from ([i] + a for a in _enumuerate_a(i, depth + 1))
    yield from _enumuerate_a(0, 0)

def main():
    n, m, q = read_list(int)
    qs = []
    for i in range(q):
        qi = Q(*read_list(int))
        qs.append(qi)
    
    max_dsum = 0
    for a in enumerate_a(n):
        dsum = 0
        for q in qs:
            if a[q.b - 1] - a[q.a - 1] == q.c:
                dsum += q.d
        max_dsum = max(dsum, max_dsum)
    print(max_dsum)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

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

ans = 0
_N = N
if N < M:
    _N = M

for A in combinations_with_replacement(range(1, M + 1), _N):
    tmp = 0
    for a, b, c, d in L:
        if a < _N and b < _N and A[b - 1] - A[a - 1] == c:
            tmp += d

    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Wrong Answer

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def new_A(A):
  for i in range(N):
    if A[N-i-1] < M:
      A[N-i-1] += 1
      break
    elif A[N-i-1] == M and A[N-i-2] < M:
      A[N-i-2] += 1
      for x in A[N-i-1:]:
        x = A[N-i-2]
      break
  return A

for j in range(cmb(N+M-1, N)):
  sum = 0
  for k in range(Q):
    if A[List[k][1]-1] - A[List[k][0]-1] == List[k][2]:
      sum += List[k][3]
  if ans < sum:
    ans = sum
  A = new_A(A)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations_with_replacement
import copy
def f(A, x, N, A_list):
    if len(A) == N:
        A_list.append(A)
        return
    A.append(x)
    for i in range(x, 11):
        A_copy = copy.copy(A)
        f(A_copy, i, N, A_list)
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(range(1, M+1), N)
    A_list = []
    f([], 1, N, A_list)
    ans = 0
    for Ai in A_list:
        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()

Submission status: Wrong Answer

Solution code:
import sys
import os
import math
import bisect
import collections
import itertools

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M, Q = il()
    abcd = [il() for _ in range(Q)]

    ret = 0
    for i in itertools.combinations(range(1, M + 1), N):
        tmp = 0
        for a, b, c, d in abcd:
            if i[b - 1] - i[a - 1] == c: tmp += d

        ret = max(ret, tmp)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def new_A(A):
  for i in range(N):
    if A[N-i-1] < M:
      A[N-i-1] += 1
      break
  return A

for j in range(cmb(N+M-1, N)):
  sum = 0
  for k in range(Q):
    if A[List[k][1]-1] - A[List[k][0]-1] == List[k][2]:
      sum += List[k][3]
  if ans < sum:
    ans = sum
  A = new_A(A)
print(ans)

Submission status: Wrong Answer

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

def countup(l, n, m):
  l[n] += 1
  if l[n] > m:
    if n == 0:
      return
    l[n] -= 1
    countup(l, n-1, m)
  return

while(li[0]==1):
  pt = 0
  for i in range(Q):
    if (li[b[i]]-li[a[i]]==c[i]):
      pt += d[i]
  ans = max(ans, pt)
  countup(li, N, M)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import functools
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, M: int, Q: int,
          a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):

    # 全列挙行けるかを確認
    # @functools.lru_cache(maxsize=None)
    # def f(n, m):
    #     if n == 1:
    #         return m
    #     ret = 0
    #     for i in range(m, 0, -1):
    #         ret += f(n-1, i)
    #     return ret
    # print(f(10, 10))

    samples = []
    # 全列挙

    def rec(curr, lower, d):
        # d: 今の深さ
        if d < N:
            for i in range(lower, M+1):
                rec(curr+[i], i, d+1)
        else:
            for i in range(lower, M+1):
                samples.append(curr+[i])

    max_tot = -INF
    rec([], 0, 1)
    for A in samples:  # 10^5程度のループ
        tot = 0
        for aa, bb, cc, dd in zip(a, b, c, d):
            if A[bb-1] - A[aa-1] == cc:
                tot += dd
        max_tot = max(tot, max_tot)
    print(max_tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) 
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())

ans = 0
def dfs(L):
    global ans
    if len(L) == N+1:
        sumnum = 0
        for i in range(Q):
            if L[b[i]] - L[a[i]]==c[i]:
                sumnum += d[i]
        ans = max(ans, sumnum)
        return 0
    
    L.append(L[-1])
    A = L.copy()
    while A[-1] <= M:
        dfs(A)
        A[-1]+=1

dfs([1])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = 0

def check(A):
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    ans = max(ans, max_)

def suretu(A=[], st=1):
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(st, 11):
        if len(A) == n: # 数列完成
            check(A)
            return
        else:
            suretu(A + [i], i)

    return ans

print(suretu())

Submission status: Wrong Answer

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by1,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by1)
    c.append(cy)
    d.append(dy)
s=0
smax=-100

sys.setrecursionlimit(3000)



def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
        if s>smax:
            smax=s

        return
    
    for i in range(0,m-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[1]
dfs(sta)
print(smax)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = 0

def check(A):
    """ 数列の点数計算
    @ A: 数列
    """
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    ans = max(ans, max_)

def suretu(A=[], st=1):
    """ 数列の作成
    @ A: 作りかけの数列
    """
    
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(st, 11):
        if len(A) == n: # 数列完成
            check(A)
            return
        else:
            suretu(A + [i], i)

    return ans

print(suretu())

Submission status: Wrong Answer

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by)
    c.append(cy)
    d.append(dy)
s=0
smax=-100

sys.setrecursionlimit(3000)



def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
        if s>smax:
            smax=s

        return
    
    for i in range(0,n+2-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[0]
dfs(sta)
print(smax)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = -1

def check(A):
    """ 数列の点数計算
    @ A: 数列
    """
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    ans = max(ans, max_)

def suretu(A=[], st=1):
    """ 数列の作成
    @ A: 作りかけの数列
    """
    
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(st, 11):
        if len(A) == n: # 数列完成
            check(A)
            return
        else:
            suretu(A + [i], i)

    return ans

print(suretu())

Submission status: Wrong Answer

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by)
    c.append(cy)
    d.append(dy)
s=0
smax=-100

sys.setrecursionlimit(3000)



def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
            if s>smax:
                smax=s

        return
    
    for i in range(0,n+2-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[0]
dfs(sta)
print(smax)

Submission status: Wrong Answer

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by)
    c.append(cy)
    d.append(dy)
s=0
smax=0

sys.setrecursionlimit(3000)
#print(sys.getrecursionlimit())


def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
            if s>smax:
                smax=s

        return
    
    for i in range(0,n+2-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[0]
dfs(sta)
print(smax)

Submission status: Wrong Answer

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


a=[]
b=[]
c=[]
d=[]
for i in range(0,q):
    ay,by,cy,dy=map(int,input().split())
    a.append(ay)
    b.append(by)
    c.append(cy)
    d.append(dy)
s=0
smax=0

sys.setrecursionlimit(3000)
print(sys.getrecursionlimit())


def dfs(h):
    global smax
    if len(h)==n+1:
        s=0
        for j in range(0,q):
            if h[b[j]]-h[a[j]]==c[j]:
                s+=d[j]
            if s>smax:
                smax=s

        return
    
    for i in range(0,n+2-h[len(h)-1]):
        
        h2=h[:]
        h2.append(h[len(h)-1]+i)
        dfs(h2)

sta=[0]
dfs(sta)
print(smax)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = -1

def check(A):
    """ 数列の点数計算
    @ A: 数列
    """
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    ans = max(ans, max_)

def suretu(A=[]):
    """ 数列の作成
    @ A: 作りかけの数列
    """
    if len(A) == n: # 数列完成
        check(A)
        return
    
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(1, 11):
        if i >= (A[-1] if A else -1):
            suretu(A + [i])

    return ans

print(suretu())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def dfs(k, x):
    global mx
    if k == n:
        v = 0
        for line in query:
            a, b, c, d = line
            if x[b] - x[a] == c: v += d
        if mx < v: mx = v
    else:
        for i in range(x[-1], m + 1):
            dfs(k + 1, x + [i])
    
mx = 0
dfs(0, [0])

print(mx)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n,m,q = map(int,input().split())
item = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    item.append([a,b,c,d])
a = [0 for i in range(11)]
ans = 0
for i1 in range(1,11):
    a[1] = i1
    for i2 in range(i1,m+1):
        a[2] = i2
        for i3 in range(i2,m+1):
            a[3] = i3
            for i4 in range(i3,m+1):
                a[4] = i4
                for i5 in range(i4,m+1):
                    a[5] = i5
                    for i6 in range(i5,m+1):
                        a[6] = i6
                        for i7 in range(i6,m+1):
                            a[7] = i7
                            for i8 in range(i7,m+1):
                                a[8] = i8
                                for i9 in range(i8,m+1):
                                    a[9] = i9
                                    for i10 in range(i9,m+1):
                                        a[10] = i10
                                        s = 0
                                        for e,f,g,h in item:
                                            if a[f-1] - a[e-1] == g:
                                                s+=h
                                        ans = max(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n,m,q = map(int,input().split())
item = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    item.append([a,b,c,d])
a = [0 for i in range(11)]
ans = 0
for i1 in range(1,11):
    a[1] = i1
    for i2 in range(i1,m+1):
        a[2] = i2
        for i3 in range(i2,m+1):
            a[3] = i3
            for i4 in range(i3,m+1):
                a[4] = i4
                for i5 in range(i4,m+1):
                    a[5] = i5
                    for i6 in range(i5,m+1):
                        a[6] = i6
                        for i7 in range(i6,m+1):
                            a[7] = i7
                            for i8 in range(i7,m+1):
                                a[8] = i8
                                for i9 in range(i8,m+1):
                                    a[9] = i9
                                    for i10 in range(i9,m+1):
                                        a[10] = i10
                                        s = 0
                                        for e,f,g,h in item:
                                            if a[f-1] - a[e-1] == g:
                                                s+=h
                                            ans = max(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:


from functools import lru_cache

n, m, q = map(int, input().split())
abc2d = {}
a2bcd = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d
    a2bcd.setdefault(a, [])
    a2bcd[a].append((b,c,d))

a = [0] * n # 各要素は0,1,...,m-1
best = 0

@lru_cache(2**20)
def value(ind, *tmp_a):
    # a[ind:]についての目的関数値, *tmp_aはa[ind](=0), a[ind+1],...が入る
    val = 0
    if ind in a2bcd:
        val = value(ind+1, *(item-tmp_a[0] for item in tmp_a[1:]))
        for bb,cc,dd in a2bcd[ind]:            
            if tmp_a[bb-ind] - tmp_a[0] == cc:
                val += dd
#     print(tmp_a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(0,*a)
        best = max(best, val)
        return
    for v in range(a[ind], m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, q  = map(int, input().split())
abcd  = [tuple(map(int, input().split())) for i in range(q)]

ans = -1

def check(A):
    """ 数列の点数計算
    @ A: 数列
    """
    A = list(map(int, list(A)))
    global ans
    max_ = 0

    # 点数計算
    for (a, b, c, d) in abcd:
        if A[b-1] - A[a-1] == c:
            max_ += d

    # 最大値更新
    if ans < max_:
        ans = max_

def suretu(A=''):
    """ 数列の作成
    @ A: 作りかけの数列
    """
    if len(A) == n: # 数列完成
        #if A[0] != '0':
        check(A)
        return
    
    # 再帰的に数字を1つずつ足してって数列生成
    for i in range(10):
        if len(A) == 0:
            suretu(str(i))
        else:
            if i >= int(A[-1]):
                suretu(A + str(i))

suretu()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n, m, q = map(int,input().split())
max = 0
j = []
for i in range(q):
    aa,b,c,d = map(int,input().split())
    j.append([aa,b,c,d])

a = [0 for k in range(11)]
for i1 in range(1,11):
    a[1] = i1
    for i2 in range(i1,11):
        a[2] = i2
        for i3 in range(i2,11):
            a[3] = i3
            for i4 in range(i3,11):
                a[4] = i4
                for i5 in range(i4,11):
                    a[5] = i5
                    for i6 in range(i5,11):
                        a[6] = i6
                        for i7 in range(i6,11):
                            a[7] = i7
                            for i8 in range(i7,11):
                                a[8] = i8
                                for i9 in range(i8,11):
                                    a[9] = i9
                                    for i10 in range(i9,11):
                                        a[10] = i10
                                        s = 0
                                        for i in j:
                                            if a[i[1]]-a[i[0]] == i[2]:
                                                s += i[3]
                                        if max < s:
                                            max = s

print(max)

Submission status: Wrong Answer

Solution code:


from functools import lru_cache

n, m, q = map(int, input().split())
abc2d = {}
a2bcd = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d
    a2bcd.setdefault(a, [])
    a2bcd[a].append((b,c,d))

a = [0] * n # 各要素は0,1,...,m-1
best = 0

@lru_cache(2**20)
def value(ind, *tmp_a):
    # a[ind:]についての目的関数値, *tmp_aはa[ind](=0), a[ind+1],...が入る
    val = 0
    if ind in a2bcd:
        val = value(ind+1, *(item-tmp_a[0] for item in tmp_a[1:]))
        for bb,cc,dd in a2bcd[ind]:            
            if tmp_a[bb-ind] - tmp_a[0] == cc:
                val += dd
#     print(tmp_a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(0,*a)
        best = max(best, val)
        return
    for v in range(m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Wrong Answer

Solution code:


from functools import lru_cache

n, m, q = map(int, input().split())
abc2d = {}
a2bcd = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d
    a2bcd.setdefault(a, [])
    a2bcd[a].append((b,c,d))

a = [0] * n # 各要素は0,1,...,m-1
best = 0

@lru_cache(2**20)
def value(ind, *tmp_a):
    # a[ind:]についての目的関数値, *tmp_aはa[ind](=0), a[ind+1],...が入る
    val = 0
    if ind in a2bcd:
        val = value(ind+1, *(item-tmp_a[0] for item in tmp_a[1:]))
        for bb,cc,dd in a2bcd[ind]:            
            if tmp_a[bb-ind] - tmp_a[0] == cc:
                val += dd
    print(tmp_a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(0,*a)
        best = max(best, val)
        return
    for v in range(m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Wrong Answer

Solution code:
n, m, q = list(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())

ans = 0
def dfs(A=[]):
    global ans
    if len(A) == n+1:
        now = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        ans = max(ans, now)
        return
    A.append(A[-1])
    while(A[-1] <= m):
        dfs(A)
        A[-1] += 1

dfs([1])
print(ans)

Submission status: Wrong Answer

Solution code:


n, m, q = map(int, input().split())
abc2d = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d

a = [0] * n # 各要素は0,1,...,m-1
best = 0
def value(a):
    val = 0
    for (aa,bb,cc),v in abc2d.items():
        if a[bb] - a[aa] == cc:
            val += v
#     print(a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(a)
        best = max(best, val)
        return
    for v in range(m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Wrong Answer

Solution code:


n, m, q = map(int, input().split())
abc2d = {}
for i in range(q):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    abc2d[a,b,c] = d

a = [0] * n # 各要素は0,1,...,m-1
best = 0
def value(a):
    val = 0
    for (aa,bb,cc),v in abc2d.items():
        if a[bb] - a[aa] == cc:
            val += v
    print(a, val)
    return val

def sub(a,ind):
    global best
    # a[ind:]について全探索
    if ind==n:
        val = value(a)
        best = max(best, val)
        return
    for v in range(m):
        a[ind] = v
        sub(a, ind+1)
sub(a, 1)
print(best)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 20:59:14 2020
"""

import sys
#import numpy as np
import itertools
sys.setrecursionlimit(10 ** 9)

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

A = itertools.combinations_with_replacement([i for i in range(1,M)],N)

ans = 0
for l in A:
    tmp = 0
    for a,b,c,d in abcd:
        if l[b-1] - l[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)