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())
check = list()
for i in range(Q):
  check.append(list(map(int, input().split())))
ans = 0
A = [1] * N
A[0] = 1
for i1 in range(1, M+1):
  A[1] = i1
  if(N >= 3):
    for i2 in range(i1, M+1):
      A[2] = i2
      if(N >= 4):
        for i3 in range(i2, M+1):
          A[3] = i3
          if(N >= 5):
            for i4 in range(i3, M+1):
              A[4] = i4
              if(N >= 6):
                for i5 in range(i4, M+1):
                  A[5] = i5
                  if(N >= 7):
                    for i6 in range(i5, M+1):
                      A[6] = i6
                      if(N >= 8):
                        for i7 in range(i6, M+1):
                          A[7] = i7
                          if(N >= 9):
                            for i8 in range(i7, M+1):
                              A[8] = i8
                              if(N >= 10):
                                for i9 in range(i8, M+1):
                                  A[9] = i9
                                  tmp = 0
                                  for i in range(Q):
                                    a = check[i][0]
                                    b = check[i][1]
                                    c = check[i][2]
                                    d = check[i][3]
                                    if(A[b-1]-A[a-1] == c):
                                      tmp += d
                                  ans = max(ans, tmp)
                              else:
                                tmp = 0
                                for i in range(Q):
                                  a = check[i][0]
                                  b = check[i][1]
                                  c = check[i][2]
                                  d = check[i][3]
                                  if(A[b-1]-A[a-1] == c):
                                    tmp += d
                                ans = max(ans, tmp)
                          else:
                            tmp = 0
                            for i in range(Q):
                              a = check[i][0]
                              b = check[i][1]
                              c = check[i][2]
                              d = check[i][3]
                              if(A[b-1]-A[a-1] == c):
                                tmp += d
                            ans = max(ans, tmp)
                      else:
                        tmp = 0
                        for i in range(Q):
                          a = check[i][0]
                          b = check[i][1]
                          c = check[i][2]
                          d = check[i][3]
                          if(A[b-1]-A[a-1] == c):
                            tmp += d
                        ans = max(ans, tmp)
                  else:
                    tmp = 0
                    for i in range(Q):
                      a = check[i][0]
                      b = check[i][1]
                      c = check[i][2]
                      d = check[i][3]
                      if(A[b-1]-A[a-1] == c):
                        tmp += d
                    ans = max(ans, tmp)
              else:
                tmp = 0
                for i in range(Q):
                  a = check[i][0]
                  b = check[i][1]
                  c = check[i][2]
                  d = check[i][3]
                  if(A[b-1]-A[a-1] == c):
                    tmp += d
                ans = max(ans, tmp)
          else:
            tmp = 0
            for i in range(Q):
              a = check[i][0]
              b = check[i][1]
              c = check[i][2]
              d = check[i][3]
              if(A[b-1]-A[a-1] == c):
                tmp += d
            ans = max(ans, tmp)
      else:
        tmp = 0
        for i in range(Q):
          a = check[i][0]
          b = check[i][1]
          c = check[i][2]
          d = check[i][3]
          if(A[b-1]-A[a-1] == c):
            tmp += d
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

abcd = []
memo = []
N, M, Q = inpl()
for i in range(0,Q):
  abcd.append(inpl())
  
abcd.sort(key = lambda x:x[3] ,reverse = True)

for a,b,c,d in abcd:
  jj = 0
  if len(memo) == 0:
  	memo.append([a,b,c,d])
  else:
    for aa,bb,cc,dd in memo:
      if  (aa <= a and b < bb) or (aa < a and b <= bb):
        if c <= cc:
          break
        else:
          jj = 1
      elif aa == a and bb == b:
        if c == cc:
          break
        else:
          jj = 1
      elif (a <= aa and bb < b) or (a < aa and bb <= b):
        if c >= cc:
          break
        else:
          jj = 1
      elif bb == a:
        ttt = [aa, b, cc +c]
        for aaa,bbb,ccc,_ in memo:
          if  (aaa <= aa and b < bbb) or (aaa < aa and b <= bbb):
            if cc+c <= ccc:
              break
            else:
              jj = 1
          elif aaa == aa and bbb == bb:
            if c+cc == ccc:
              break
            else:
              jj = 1
          elif (aa <= aaa and bbb < b) or (aa < aaa and bbb <= b):
            if c+cc >= ccc:
              break
            else:
              jj = 1
    if jj == 0:
      memo.append([a,b,c,d])

sum = 0
for m in memo:
  sum += m[3]
  
print(sum)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time



def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def rec(li, i, M, N, a, b, c, d, cans):
    # print(i, li, len(li), N)
    if len(li) >= N:
        # print(li, N)
        ans = 0
        for j in range(len(a)):
            if li[b[j]-1] - li[a[j]-1] == c[j]:
                ans += d[j]
        # print(ans, li)
        return ans

    # for j in range(1, len(lis[i])):
    #     for v in lis[i][j]:

    ans = 0
    if len(cans[i]) == 0:
        ans = max(ans, rec(li + [1], i+1, M, N, a, b, c, d, cans))
    else:
        for v in cans[i]:
            ans = max(ans, rec(li + [v], i+1, M, N, a, b, c, d, cans))

    return ans


def main():
    N, M, Q = MI()
    a = [0] * Q
    b = [0] * Q
    c = [0] * Q
    d = [0] * Q
    didx = [None] * Q
    lis = [[[] for i in range(N+1)] for i in range(N+1)]
    cans = [set() for i in range(N+1)]

    for i in range(Q):
        a[i], b[i], c[i], d[i] = MI()
        # didx[i] = (d[i], i)

    # cans = []
    # for i in range(1, M+1):
    #     cans += [i] * N

    # for li in combinations(cans, N):
    #     print(li)

    # didx.sort(reverse=True)

    for i in range(Q):
        # lis[b[i]][a[i]].append(c[i])
        lis[a[i]][b[i]].append(c[i])

    for i in range(1, N):
        cans[i].add(1)

    for i in range(1, N+1):
        # print(i, lis[i])
        for j in range(len(lis[i])):
            for k in lis[i][j]:
                for v in cans[i]:
                    # print(v, k)
                    if v + k <= M:
                        cans[j].add(v + k)
    # print(cans)
    # print(didx)
    print(rec([], 1, M, N, a, b, c, d, cans))
    # print(sum(d))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

query = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    query.append([a, b, c, d])


def calcPoint(num):
    ret = 0
    for q in range(Q):
        if num[query[q][1] - 1] - num[query[q][0] - 1] == query[q][2]:
            ret += query[q][3]

    return ret


suu = [0] * N
now = [0] * N
nowPoint = 0
ans = 0


def dsf(now, nextt):
    global ans
    if nextt >= Q:
        return

    ans = max(ans, calcPoint(now))

    temp = now.copy()
    temp2 = now.copy()

    temp[query[nextt][1] - 1] = temp[query[nextt][0] - 1] + query[nextt][2]
    dsf(temp, nextt + 1)
    dsf(temp2, nextt + 1)


dsf(suu, 0)
print(ans)

Submission status: Wrong Answer

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

kumi.sort(key=lambda x: x[1])
kumi.sort(key=lambda x: x[0])

lst = []
for i in range(q):
    ai, bi, ci, di = kumi[i]
    if ai == 1 and bi == 2:
        lst.append(str(ci))
lst.append('0')

num = 0
ans = 0
while num <= 10**(n-2)-1:
    str_num = str(num)
    pad = str_num.zfill(n-2)
    for ci in lst:
        if int(ci) > int(pad[0]): continue
        temp_pad = '0' + ci + pad
        temp = 0
        for i in range(q):
            ai, bi, ci, di = kumi[i]
            ai, bi = ai-1, bi-1
            if int(temp_pad[bi]) - int(temp_pad[ai]) == ci:
                temp += di
    ans = max(ans, temp)
    # 数の更新
    if pad[-1] == 9:
        num += 1
        str_num = str(num)
        pad = str_num.zfill(n-2)
        next_num = pad[0]
        for i in range(1, n-2):
            if int(pad[i]) < int(next_num[-1]):
                next_num = next_num + next_num[-1]*(n-2-i)
                break
            else:
                next_num = next_num + pad[i]
        num = int(next_num)
    else:
        num += 1
    if num == 10**(n-2)-1: break

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import numpy as np
N, M, Q =  map(int, input().split())
array = np.linspace(1, M, M)
data = [input().split() for _ in range(int(Q))]
data = np.array(data).astype(int)

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)
c = combinations(array, N)
l = np.empty((0, N))
for i in c :
    i = np.array(i).reshape(1, N)
    l = np.concatenate([l, i])
ans = 0
for i in data:
    dd = l[:, (i[1] - 1)] - l[:, (i[0] - 1)]
    ee = np.where((dd == i[2]))[0]
    print(print(dd, i[2]))
    if len(ee) > 0:
        ans += i[3]
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)]

max = 0
a = ['1']*N
b = [str(M)]*N
a = int(''.join(a))
b = int(''.join(b))

for x in range(a,b+1):
	x=str(x)
	tmp_sum=0
	for i in range(Q):
		if int(x[abcd[i][1]-1])-int(x[abcd[i][0]-1])==abcd[i][2]:
			tmp_sum+=abcd[i][3]
	if max<tmp_sum:
		max=tmp_sum
print(max)

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

A = sorted(A, key=lambda x: x[0])

ref = [[1]*n + [0]]

for a in A:
    nxt = []
    for b in ref:
        temp = b.copy()
        if temp[a[1]-1] == 1:
            temp[a[1]-1] += a[2] + temp[a[0]-1]
            temp[n] += a[3]
        elif temp[a[1]-1] == a[2] + temp[a[0]-1]:
            temp[n] += a[3]
        else:
            continue
        if temp[a[1]-1] < temp[a[1]-2]:
            continue
        if temp[a[1]-1]>m:
            continue
        if a[0]>=2 and temp[a[0]-1] < temp[a[0]-2]:
            continue
        nxt.append(temp)
    ref.extend(nxt)

print(max([ref[i][n] for i in range(len(ref))]))

Submission status: Wrong Answer

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

for i in range(Q):
    n_list = [int(x) for x in input().split()]
    q_list.append(n_list)

A_list = []
for i in range(1, M):
    A_init = []
    for j in range(N):
        A_init.append(i)
    while A_init[0] < M:
        for k in range(N):
            while A_init[-1-k] < M:
                A_true = A_init.copy()
                A_list.append(A_true)
                A_init[-1-k] = A_init[-1-k] + 1
A_fin = []
for i in range(N):
    A_fin.append(M)
A_list.append(A_fin)

tem_max = 0
for A in A_list:
    q_max = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            q_max += q[3]
    if tem_max < q_max:
        tem_max = q_max
print(tem_max)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from itertools import combinations_with_replacement

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

x = [_ for _ in range(1, M+1)]
y = list(combinations(x, N))
#y = list(combinations_with_replacement(x, N))

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

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

Submission status: Wrong Answer

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

ans=0

for i in range(2**Q):
    s=bin(i)
    p=[P[j] for j in range(len(s)-2) if int(s[2+j])==1]
    min_s = [[0] * N for _ in range(N)]
    max_s = [[M-1] * N for _ in range(N)]
    flg=True
    for i in range(0, len(p)):
        a = p[i][0]
        b = p[i][1]
        c = p[i][2]
        a -= 1
        b -= 1
        if c >= min_s[a][b] and c <= max_s[a][b]:
            for j in range(a, b + 1):
                min_s[a][j] = max(min_s[a][j], P[i][2])
            for j in range(b, N):
                max_s[a][j] = min(min_s[a][j], P[i][2])
        else:
            flg=False
    if flg:
        ans=max(ans, sum([p[k][3] for k in range(len(p))]))
print(ans)

Submission status: Wrong Answer

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


def main():
    n, m, q = map(int,input().split())
    A = [input().split() for i in range(q)]

    #k = int(input())
    lists = []

    for i in range(m):
      for j in range(n):
         lists.append(int(i+1))
    
    if n > 7:
        j = 2
    else:
        j = n
    
    lists = list(combinations_with_replacement(lists,n))
    lists = sorted(set(lists))
    print(lists)
    
    tokuten = 0
    for l in lists:
        d = 0
        for a in A:
            if l[int(a[1])-1] - l[int(a[0])-1] == int(a[2]):
                d = d + int(a[3])
        if d > tokuten:
            tokuten = d
    
    print(tokuten)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q=map(int,input().split(" "))
l=[]
a=[]
b=[]
c=[]
d=[]
g=0

for i in range(m):
  l.append(int(i+1))

for i in range(q):
  line=input().split(" ")
  a.append(int(line[0]))
  b.append(int(line[1]))
  c.append(int(line[2]))
  d.append(int(line[3]))
  
for v in list(itertools.combinations(l,n)):
  f=0
  for i in range(q):
    if int(v[b[i]-1])-int(v[a[i]-1])==c[i]:
      f=f+d[i]
  if g<f:
    g=f
print(g)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q = map(int,input().split())
L = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    L.append([a,b,c,d])
ans = 0
cur = [i for i in range(q)]
for i in range(1,q+1):
    temp = list(itertools.combinations(cur,i))
    for j in range(len(temp)):
        now = temp[j]
        dp = [0 for i in range(n)]
        score = 0
        flag = True
        changed = [False]*n
        look = []
        for k in range(len(temp[j])):
            a = L[now[k]][0]
            b = L[now[k]][1]
            c = L[now[k]][2]
            d = L[now[k]][3]
            look.append([a,b,c,d])
        look.sort()
        for k in range(len(look)):
            a = look[k][0]
            b = look[k][1]
            c = look[k][2]
            d = look[k][3]
            if changed[a-1] == False and changed[b-1] == False:
                changed[a-1] = True
                for l in range(b-1,n):
                    if changed[l] == False:
                        changed[l] == True
                        dp[l] = dp[a-1]+c
                    else:
                        if dp[l] == dp[a-1]+c and l == b-1:
                            None
                        elif dp[l] != dp[a-1]+c and l == d-1:
                            flag = False
                        elif dp[l] >= dp[a-1]+c:
                            None
                        else:
                            flag = False
                            break
                score += d
            elif changed[a-1] == True and changed[b-1] == False:
                for l in range(b-1,n):
                    if changed[l] == False:
                        changed[l] == True
                        dp[l] = dp[a-1]+c
                    else:
                        if dp[l] == dp[a-1]+c and l == b-1:
                            None
                        elif dp[l] != dp[a-1]+c and l == d-1:
                            flag = False
                        elif dp[l] >= dp[a-1]+c:
                            None
                        else:
                            flag = False
                            break
                score += d
            elif changed[a-1] == False and changed[b-1] == True:
                changed[a-1] = True
                dp[a-1] = dp[b-1]-c
                score += d
            else:
                if dp[b-1]-c != dp[a-1]:
                    flag = False
                    break
                else:
                    score += d
        for k in range(n-1):
            if dp[k] <= dp[k+1]:
                None
            else:
                flag = False
                break
        if flag == True and dp[n-1]-dp[0] <= m-1:
            ans = max(ans,score)
        else:
            None
print(ans)

Submission status: Wrong Answer

Solution code:
# 条件を全て上げる
from itertools import combinations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
INF = 10 ** 10
def check(comb):
    if len(comb) == 1: return True
    comb.sort(key=lambda x:x[2], reverse=True)
    # 与えられた条件の配列が作成可能か判定する
    ret = [0] * N
    for a, b, c, d in comb:
        ret[a-1] = ret[b-1] - c
    for a, b, c, d in comb:
        if ret[b-1] - ret[a-1] != c: return False
    return True

ans = max([c[3] for c in abcd])
for i in range(2,10):
    for comb in combinations(abcd, i):
        if len(comb) == 4:
            t = 3
        if check(list(comb)):
            ans = max(ans, sum([c[3] for c in comb]))

print(ans)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

Solution code:
def gen(size, max):
    res = []

    s = [1] * size
    s[size-1] = max

    for i in range(size-1, 0, -1):
        for j in range(1, max+1):

            tmp = s[0:size]
            tmp[i] = j
            res.append(tmp)
            s = tmp
    return res


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

Arr = []
for i in range(Q):
    a, b, c, d = map(int, input().strip().split())
    Arr.append([a, b, c, d])

max = 0
x = gen(N, M)

for i in x:
    now = 0
    for j in range(Q):
        if i[Arr[j][1]-1]-i[Arr[j][0]-1] == Arr[j][2]:
            now += Arr[j][3]
    if now > max:
        max = now

print(max)

Submission status: Wrong Answer

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

A = [1]*N
ans = 0
while A[0] == 1:
    A[N-1] += 1
    tmp = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1]==c: tmp += d
    ans = max(ans,tmp)
    for i in range(N-1,-1,-1):
        if A[i]>M:
            A[i-1] += 1
            for j in range(i,N):
                A[j] = A[i-1]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
a = []
b = []
c = []
d = []
for i in range(q):
    e,f,g,h = map(int,input().split())
    if g == 0:
        continue
    a.append(e)
    b.append(f)
    c.append(g)
    d.append(h)

counter = 0
for i in range(n-1):
    counter += m - 1
    m -= 1

sum_c = 0
count = 0
for i in sorted(c):
    sum_c += i
    if sum_c > counter:
        break
    count += 1
#print(count)
d_count = 1
ans = 0
for i in sorted(d,reverse = True):
    if d_count > count:
        break
    ans += i
    d_count += 1


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

max_val = 0
n = N
m = M
l = [i+1 for i in range(M)]
# print(l)
for v in itertools.combinations(l,n):
    # print(v)
    val = 0
    for q in range(Q):
        a = AA[q][0]-1
        b = AA[q][1]-1
        # print('a',a)
        # print('b',b)
        # print('lb',v[b])
        # print('la',v[a])
        # print('sabun',v[b]-v[a])
        # print('c',AA[q][2])
        # print('d',AA[q][3])
        if(v[b]-v[a] == AA[q][2]):
            val += AA[q][3]
            # print('add')
    # print('value',val)
    if val > max_val:
        max_val = val

print(max_val)

Submission status: Wrong Answer

Solution code:
# ABC165 C

import itertools

def main():
    n, m, q = map(int, input().split())
    List = []
    for i in range(q):
        a, b, c, d = map(int, input().split())
        List.append([a, b, c, d])
    
    max_total = 0

    for A in list(itertools.combinations(range(1, m+1),n)):
        total = 0
        for abcd in List:
            if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
                total += abcd[3]
        #print(total)
        if total >= max_total:
            max_total = total
    
    print(max_total)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def number(keta,m,max_x,s,lis):
    if keta!=1:
        for i in range(max_x,m+1):
            s=s+str(i)
            number(keta-1,m,max(max_x,i),s,lis)
            s=s[:-1]
    else:
        for i in range(max_x,m+1):
            lis.append(s+str(i))

def make_list(n,m):
    global lis,s
    lis=[]
    s=""
    number(n,m,1,s,lis)
    return lis

def main():
    n,m,q=map(int,input().split())
    lis=make_list(n,m)
    ans=0
    Q=[[int(_) for _ in input().split()] for i in range(q)]

    for l in lis:
        cunt=0
        for q in Q:
            if int(l[q[1]-1])-int(l[q[0]-1])==q[2]:
                cunt+=q[3]
        ans=max(ans,cunt)

    print(ans)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

setrecursionlimit(10 ** 9)

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

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

for q in range(Q):
    abcd[q][3] *= - 1

A = [-1 for _ in range(N + 1)]

abcd.sort(key=lambda x: x[1] - x[0])

for q in range(Q):
    a, b, c, d = abcd[q]

    if A[a] == -1:
        if A[b] == -1:
            A[a] = max(1, A[a - 1])
            A[b] = c + A[a]
        else:
            A[a] = max(1, A[b] - c, A[a - 1])
    if A[b] == -1:
        A[b] = c + A[a]

ans = 0

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

print(ans * (-1))

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.sort()

DP = [0 for i in range(N+1)]
for i in range(1,N+1):
    for req in abcd:
        if req[0]==i:
            DP[req[1]] = max(DP[req[1]],DP[i]+req[3])
    print(DP)
print(max(DP))

Submission status: Wrong Answer

Solution code:
import math
import itertools

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





def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))



All =[0] * M
for i in range(M):
    All[i] = i+1

#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。
#Nの値が小さそうなので全検索でもいけるかもしれへん。



#M個のうちからN個取り出す順列
ans = 0
#for A in itertools.combinations(All, N):
for A in itertools.product(All, repeat=N):
    
    
    #点数計算
    #print(A)
    wa = 0
    for i in range(Q):
        #print(wa) 
        kari = A[b[i]-1] - A[a[i]-1]
        if kari == c[i]:
            wa = wa + d[i] 
    if ans < wa:
        ans = wa
    #print(ans) 
    #print(wa) 


print(ans)

Submission status: Wrong Answer

Solution code:
score = 0


def dfs(arr, fix, op, idx, point):

    if idx >= len(op):
        global score
        score = max(score, point)
        return

    a, b, c, d = op[idx]

    value = arr[a] + c
    if value <= m and (arr[b] == value or arr[b] == 1) and fix[b] is False:
        org = arr[b]
        arr[b] = value
        point += d
        fix[b] = True
        dfs(arr, fix, op, idx + 1, point)
        #arr[b] = org
        #point -= c

    else:
        dfs(arr, fix, op, idx + 1, point)

    return


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

op = []

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

op.sort()

for i in range(len(op)):
    a = [1] * (n + 1)
    fix = [False] * (n + 1)
    dfs(a, fix, op, 0, 0)
    op.append(op.pop(0))

print(score)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [1 for i in range(N)]
for A in itertools.product(range(A[0],M+1),repeat=N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, M, Q = (int(x) for x in input().split())
# S = [list(int(x)) for i in range(Q) for x in input().split()]
S = np.array([list(map(int,input().split(" "))) for i in range(Q)])
print(S)
# T = S[:,2]
# print(T)
sum = np.zeros(M)

for i in range(M):
    a = 0
    for j in range(Q):
        if S[j,2] == i:
            a = max(a, S[j,3])
            # print('{} {} {} {} {} {}'.format(i, j, k, S[j,2], S[j,3], sum[k]))
        sum[i] = a

print(math.floor(np.sum(sum)))

Submission status: Wrong Answer

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

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


A_list =[-1] * N
sum_max = 0

def dfs(curr, count):
    if count >= N:
        sum_ = 0
        
        for q in range(Q):
            ai = abcd_list[q][0]
            bi = abcd_list[q][1]
            ci = abcd_list[q][2]
            di = abcd_list[q][3]

            if A_list[bi - 1] - A_list[ai - 1] is ci:
                sum_ += di
        global sum_max
        if sum_max <= sum_:
            sum_max = sum_

        return

    l = N - count + 1
    # 次の値を求める
    for i in range(curr + 1, M - l + 3):
        A_list[count] = i
        dfs(i, count + 1)

dfs(0, 0)
print(sum_max)

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):
    max=d[0]
    if(N==1):
        break
        for j in range(1,N-i):
            if d[j]>max:
                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 itertools

def main():
    N, M, Q = map(int, input().split())
    origin_A = [var for var in range(1, M + 1)]
    comb_A = itertools.permutations(origin_A, N)
    max_total_d_i = 0

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

    max_total_di = 0
    for A in comb_A:
        A = sorted(A)
        total_di = 0
        for target in targets:
            if A[target[1] - 1] - A[target[0] - 1] == target[2]:
                total_di += target[3]
        if total_di > max_total_di:
            max_total_di = total_di
    print(max_total_di)

if __name__ == '__main__':
    main()