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

Submission status: Wrong Answer

Solution code:
import copy
N, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(Q):
    a_i, b_i, c_i, d_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
    c.append(c_i)
    d.append(d_i)
P = [1 for i in range(N+1)]
score = 0
abcd = [[] for i in range(Q)]
for i in range(Q):
    abcd[i].append(a[i])
    abcd[i].append(b[i])
    abcd[i].append(c[i])
    abcd[i].append(d[i])
abcd.sort(key=lambda x: x[3], reverse=True)
for i in range(Q):
    a[i] = abcd[i][0]
    b[i] = abcd[i][1]
    c[i] = abcd[i][2]
    d[i] = abcd[i][3]
    
for i in range(Q):
    R = copy.copy(P)
    S = copy.copy(P)
    R[b[i]] = R[a[i]] + c[i]
    S[a[i]] = S[b[i]] - c[i]
    score_i1 = d[i]
    score_i2 = d[i]
    if R[b[i]] > M:
        score_i1 = 0
    if S[a[i]] <= 0:
        score_i2 = 0
    for j in range(i):
        if R[b[j]] != R[a[j]] + c[j]:
            score_i1 -= d[j]
    for j in range(i):
        if S[b[j]] != S[a[j]] + c[j]:
            score_i2 -= d[j]
    if max(score_i1, score_i2) >= 0:
        if score_i1 == max(score_i1, score_i2):
            P = R
            score += score_i1
        elif score_i2 == max(score_i1, score_i2):
            P = S
            score += score_i2
print(score)

Submission status: Wrong Answer

Solution code:
import sys
import itertools


def resolve(in_):
    n, m, q = map(int, next(in_).split())
    abcd = tuple(tuple(map(int, row.split())) for row in in_)
    print(abcd)

    ans = 0
    for seq_a in itertools.combinations_with_replacement(range(1, m + 1), n):
        print(seq_a)
        point = 0
        for a, b, c, d in abcd:
            if seq_a[b - 1] - seq_a[a - 1] == c:
                point += d
        ans = max(ans, point)

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,m,q = map(int,input().split())
    chk = []
    for i in range(q):
        chk.append(list(map(int,input().split())))
    ans = 0
    a = [1 for i in range(n)]
    for i in range(n):
        for j in range(1,m+1):
            a[n-1-i] = j
            m = 0
            for k in range(q):
                if a[chk[k][1]-1]-a[chk[k][0]-1] == chk[k][2]:
                    m += chk[k][3]
            if m>ans:
                ans = m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

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


def dfs(x):
    if len(x) == N:
        res = 0
        for a, b, c, d in X:
            if x[b - 1] - x[a - 1] == c:
                res += d
        return res

    res = 0
    for i in range(1, M + 1):
        x.append(i)
        res = max(res, dfs(x))
        x.pop()

    return res


print(dfs([]))

Submission status: Wrong Answer

Solution code:
# 視点を変えてやる全探索 実は条件よりAを全列挙することが可能
n, m, q = map(int, input().split())
koho = []


def rec(arr):
    if len(arr) == n:
        koho.append(arr)
    else:
        for i in range(arr[-1], m + 1):
            nex_arr = arr[:]
            nex_arr.append(i)
            rec(nex_arr)


for i in range(m + 1):
    rec([i])
ans = 0

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

for arr in koho:
    tmp = 0
    for abcd in qs:
        if arr[abcd[1] - 1] - arr[abcd[0] - 1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N,M,Q = map(int, input().split())
    pair = []
    for i in range(Q):
        pair += list(map(int, input().split())),

    def score(A):
        nonlocal pair
        sum = 0
        for a,b,c,d in pair:
            if A[b-1] - A[a-1] == c:
                sum += d
        return sum

    ans = 0
    A = [1]*N
    i = N-1
    while A != [M]*N:
        ans = max(ans, score(A))
        while A[i] == M:
            i -= 1
        if i < 0:
            break
        A[i] += 1
        j = i
        while i <= N-1:
            A[i] = A[j]
            i += 1
        i = N-1
        
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
(N,M,Q) = map(int,input().split())
Qs = []
for i in range(Q):
    Qs.append(list(map(int,input().split())))
A = [1]*N
score = 0
while(1):
    if A[0]>M:
        break
    current_score = 0
    for i in range(Q):
        if A[Qs[i][1]-1]-A[Qs[i][0]-1] == Qs[i][2]:
            current_score += Qs[i][3]
    score = max(score,current_score)
    for i in range(1,N):
        if A[i]== M:
            A[i-1] += 1
            A[i] = A[i-1]
            break
        if i == N-1:
            A[N-1] += 1
print(score)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
a = [0 for _ in range(Q)]
b = [0 for _ in range(Q)]
c = [0 for _ in range(Q)]
d = [0 for _ in range(Q)]
for k in range(Q):
  a[k], b[k], c[k], d[k] = map(int, input().split())
A = [1 for _ in range(N)]

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

def next(A):
  k = 1
  while k < N+1:
    if A[-k] < M:
      A[-k] += 1
      return A
      break
    else:
      for j in range(1, k+1):
        A[-j] = A[-k-1] + 1
      k += 1
      
ans = 0
while A[0] < M:
  ans = max(ans, point(A))
  #print(A)
  A = next(A)

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)]
a,b,c,d = [],[],[],[]
for i in range(q):
  a.append(abcd[i][0])
  b.append(abcd[i][1])
  c.append(abcd[i][2])
  d.append(abcd[i][3])

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

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

print(dfs([0]))

Submission status: Wrong Answer

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

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

ary = [1 for _ in range(N)]
ans = 0
while ary[0] < M:
  #print(ary)
  pt = 0
  for j in range(Q):
    rq = Rq[j]
    if ary[rq[1]-1]-ary[rq[0]-1] == rq[2]:
      pt += rq[3]
  ans = max(ans,pt)
  
  #次の配列へ
  for i in range(-1, -N-1, -1):
    if ary[i] < M:
      ary[i] += 1
      tmp = ary[i]
      for l in range(i+1, 0):
        ary[l] = tmp
      break

print(ans)

Submission status: Wrong Answer

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

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

ary = [1 for _ in range(N)]
ans = 0
while ary[0] < M:
  #print(ary)
  pt = 0
  for j in range(Q):
    rq = Rq[j]
    if ary[rq[1]-1]-ary[rq[0]-1] == rq[2]:
      pt += rq[3]
  ans = max(ans,pt)
  
  #次の配列へ
  for i in range(-1, -N-1, -1):
    if ary[i] < M:
      ary[i] += 1
      tmp = ary[i]
      for j in range(i+1, 0):
        ary[j] = tmp
      break

print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[1]*N
  list[-1]=0
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  print(i)
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[1]*N
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[0]*N
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M-1:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[0]*N
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M-1:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  print(i)
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[0]*N
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>M:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

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

abcd=[]
for i in range(Q):
  abcd.append(list(map(int,input().split())))
  abcd[i][0]-=1
  abcd[i][1]-=1

  
def calcScore(target):
  score=0
  for i in range(Q):
    if target[abcd[i][1]]-target[abcd[i][0]]==abcd[i][2]:
      score+=abcd[i][3]
  return score

def makeTarget():
  list=[0]*N
  while True:
    list[-1]+=1
    for i in range(len(list)):
      if list[-i-1]>10:
        if len(list)==i+1:return
        list[-i-2]+=1
        list[-i-1]=0
    for i in range(len(list)-1):
      if list[i]>list[i+1]:list[i+1]=list[i]
    yield list.copy()

ans=0
for i in makeTarget():
  ans=max(ans,calcScore(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
s_l = []
for i in range(q):
    s = list(map(int, input().split()))
    s_l.append(s)

l = []
for i in range(1, n):
    l.append(i)

A = []
for i in range(n, m+1):
    ll = l
    for j in range(n, i+1):
        ll.append(j)
    for v in combinations_with_replacement(ll, n):
        A.append(v)

ans = 0
for a in A:
    cnt = 0
    for i in range(q):
        if a[s_l[i][1] - 1] - a[s_l[i][0] - 1] == s_l[i][2]:
            cnt += s_l[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = [int(_) for _ in input().split()]
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q

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


def calc_score(A):
    acc = 0
    for i in range(Q):
        if c[i] == A[b[i]] - A[a[i]]:
            acc += d[i]
    return acc


max_score = -1


def dfs(A):
    if len(A) == N:
        global max_score
        max_score = max(calc_score(A), max_score)
    else:
        if len(A) == 0:
            A.append(1)
        else:
            A.append(A[-1])
        while (A[-1] <= M):
            dfs(A)
            A[-1] += 1


dfs([])
print(max_score)

Submission status: Wrong Answer

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

# N = [4, 6, 10]
# Q = [[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]]

from itertools import combinations_with_replacement as comb_rplc

C = 0
for seq in comb_rplc(range(1, N[1]+1), N[0]):
    print(seq)
    S = 0
    for i in range(N[2]):
        if seq[Q[i][1]-1]-seq[Q[i][0]-1] == Q[i][2]:
            S += Q[i][3]
    if S > C:
        C = S

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def calc(li):
    score = 0
    for a, b, c, d in l:
        if li[b-1]-li[a-1] == c:
            score += d
    return score

que = deque([[i] for i in range(1, M+1)])
ans = 0

while que:
    li = que.popleft()
    if len(li) == N:
        score = calc(li)
        ans = max(ans, score)
    else:
        for i in range(len(li),M+1):
            next = li + [i]
            que.append(next)
    #print(que)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque
N, M, Q = [int(x) for x in input().split(" ")]

conditions = [[int(x) for x in input().split(" ")] for _ in range(Q)]

def get_next(l, N, ans):
    if len(l) == N:
        ans.append(l)
        return []
    b = l[-1]
    result = []
    for i in range(b, N+1):
        result.append(l + [i])
    return result

queue = deque([[x] for x in range(M)])
L = []
while len(queue) > 0:
    l = queue.pop()
    queue.extend(get_next(l, N, L))

smax = 0
for l in L:
    s = 0
    for c in conditions:
        if l[c[1]-1] - l[c[0]-1] == c[2]:
            s += c[3]
    if s > smax:
        smax = s
print(smax)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


# 昇順列の巡回
def ascending(N, M):
    # 長さM, 値0からN-1まで
    A = [0] * N
    yield A
    while True:
        # Mより小さい最後の桁
        k = None
        for i in reversed(range(N)):
            if A[i] < M:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, N):
                A[j] = A[k]
        else:
            return
        yield A


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    # 昇順列を巡回する
    ans = 0
    for a in ascending(n, m):         # O(N)
        p = point(a)
        if ans <= p:
            ans = p
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

num=1
seed = [[i] for i in range(1,m+1)]
while num!=n:
  num+=1
  tmp_list = []
  while seed:
    tmp = seed.pop()
    for i in range(tmp[-1]+1,m+1):
      tmp_list.append(tmp+[i])
  seed = tmp_list.copy()
  
max_score = 0
visited = set()
for arr in seed:
  score = 0
  for arr_2 in list_:
    if arr[arr_2[1]-1] - arr[arr_2[0]-1] == arr_2[2]:
      score+=arr_2[3]
      max_score = max(max_score, score)
print(max_score)

Submission status: Wrong Answer

Solution code:
import itertools

n,m,q = map(int, input().split())
list_ = [list(map(int, input().split())) for _ in range(q)]
tmp = list(range(1,m+1))
cases = [sorted(list(arr)) for arr in itertools.product(tmp, repeat=n)]

max_score = 0
visited = set()
for arr in cases:
  score = 0
  if str(arr) in visited:
    break
  visited.add(str(arr))
  for arr_2 in list_:
    if arr[arr_2[1]-1] - arr[arr_2[0]-1] == arr_2[2]:
      score+=arr_2[3]
  max_score = max(max_score, score)
print(max_score)

Submission status: Wrong Answer

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

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

def dfs(a_l):
  if len(a_l)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if (a_l[b]-a_l[a]==c):
        t_ans+=d
    ans=max(ans,t_ans)

    return

  a_last=a_l[-1]
  for i in range(a_last,m+1):
    dfs(a_l+[i])

ans=0
for i in range(m+1):
  dfs([i])

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

def dfs(keta,a_l):
  if len(a_l)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if (a_l[b]-a_l[a]==c):
        t_ans+=d
    ans=max(ans,t_ans)

    return

  a_last=a_l[-1]
  for i in range(a_last,m+1):
    dfs(keta+1, a_l+[i])

ans=0
for i in range(m+1):
  dfs(1,[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

abcd = [input() for _ in range(q)]

x = itertools.product(range(1,m+1),repeat=n)
tmp = 0
ans = 0
for xi in x:
  tmp = 0
  for i in abcd:
    a,b,c,d = map(int,i.split())
    if xi[b-1] - xi[a-1] == c:
      tmp += d
  ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# O(n^M) -> TLE
from itertools import product
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
arr = list(range(1, M+1))
ans = 0
for x in product(arr, repeat=N):
    cur = 0
    for y in ls:
        if x[y[1]-1] - x[y[0]-1] == y[2]:
            cur += y[3]
    ans = max(ans, cur)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from itertools import combinations_with_replacement

lis = range(1, 11)
ans = 0
for l in combinations_with_replacement(lis, N):
    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)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from itertools import combinations_with_replacement

lis = range(1, 10)
ans = 0
for l in combinations_with_replacement(lis, N):
    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)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
list = [list(map(int,input().split())) for _ in range(Q)]
seq = [i for i in range(1,M+1)]
C = combinations_with_replacement(seq, N)
max_score = 0

for A in C:
    A = sorted(A)
    score = 0
    for q in list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            score += q[3]
        print(score)
    max_score = max(score, max_score)
print(max_score)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
import numba as njit


n,m,q = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(q)]
a,b,c,d = zip(*l)

temp = np.arange(1,m+1)
A = list(itertools.product(temp, repeat=n))
ans=0

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
import numba as njit


n,m,q = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(q)]
a,b,c,d = zip(*l)

temp = np.arange(1,m+1)
A = list(itertools.product(temp, repeat=n))
ans=0


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

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools


n,m,q = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(q)]
a,b,c,d = zip(*l)

temp = np.arange(1,m+1)
A = list(itertools.product(temp, repeat=n))
ans=[]

for L in A:
  ans_temp = 0
  for j in range(q):
    if L[b[j]-1]-L[a[j]-1]==c[j]:
      ans_temp += d[j]
  ans.append(ans_temp)
print(max(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools


n,m,q = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(q)]
a,b,c,d = zip(*l)

temp = np.arange(1,m+1)
A = list(itertools.combinations(temp,n))
ans=0

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

Submission status: Wrong Answer

Solution code:
def resolve():
	from collections import deque
	N, M, Q = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(Q)]
	
	def calc(x: str) -> int:
		s = str(x)
		ans = 0
		for i in A:
			a, b, c, d = i[0], i[1], i[2], i[3]
			if int(s[b-1]) - int(s[a-1]) == c:
				ans += d
		return ans
		
	q = deque([1])
	ans = 0
	while q:
		tmp = str(q.popleft())
		if len(tmp) == N:
			ans = max(ans, calc(tmp))
		else:
			for i in range(int(tmp[-1]), M+1):
				q.append(tmp+str(i))

	print(ans)

Submission status: Wrong Answer

Solution code:

import glob

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\165\\C'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class C(Common):

    def rec(self, A, now_index):

        point1 = 0
        point2 = 0
        if now_index == self.N-1:
            point1 = 0
            for i in self.abcd:
                if A[i[1]-1] - A[i[0]-1] == i[2]:
                    point1 += i[3]

        else:
            for i in range(A[now_index], self.M+1):
                A[now_index+1] = i
                tmp = self.rec(A, now_index+1)
                if tmp > point2:
                    point2 = tmp

        if point1 > point2:
            return point1
        return point2

    def resolve(self):

        self.N, self.M, self.Q = map(int, self.input_data().split())
        self.abcd = []

        for i in range(self.Q):
            self.abcd.append(list(map(int, self.input_data().split())))

        A = [0]*self.N

        point = self.rec(A, 0)
        print(str(point))

solver = C(REL_PATH)
solver.exec_resolve()

Submission status: Wrong Answer

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

As = []

def make(A):
  global As, N, M
  print(A)
  if len(A) == N+1:
    As.append(A)
  else:
    for i in range(A[len(A)-1], M+1):
      make(A+[i])

make([1])

maxs = 0
for A in As:
  score = 0
  for req in reqs:
    if A[req[1]] - A[req[0]] == req[2]:
      score += req[3]
  maxs = max(score, maxs)

print(maxs)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
reqs = [list(map(int, input().split())) for _ in range(Q)]
 
As = []
 
def make(A):
  global As, N, M
  if len(A) == N+1:
    As.append(A)
  else:
    for i in range(A[len(A)-1], M+1):
      A.append(i)
 
make([1])
 
max = 0
for A in As:
  score = 0
  for req in reqs:
    if A[req[1]] - A[req[0]] == req[2]:
      score += req[3]
  max = max(score, max)
 
print(max)

Submission status: Wrong Answer

Solution code:
# C - Many Requirements
N,M,Q = map(int,input().split())
q = []
for i in range(Q):
    q.append(list(map(int,input().split())))
q.sort()
dp = [[0]*(M+1) for _ in range(N+1)]
for a,b,c,d in q:
    for i in range(1,M-c+1):
        dp[b][i+c] = max(dp[b][i+c],dp[a][i]+d)
print(max(max(dp)))