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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n,m,q = map(int,input().split())
E = [list(map(int,input().split())) for i in range(q)]
def dfs(l,string):
  global ans
  if l == n: ans = max(ans,check(string));return
  for i in range(int(string[-1]),m+1):
    dfs(l+1,string+str(i))

def check(string):
  print(string)
  re = 0
  for a,b,c,d in E:
    if int(string[b])-int(string[a]) == c:
      re += d
  return re
dfs(0,"1")
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import deque
def resolve():
    N, M, Q = lr()
    ans = 0
    rest = []
    tmp = 0
    for i in range(Q):
        rest.append(lr())
    rest = deque(sorted(rest, key=lambda x: (x[1],x[0]))[::-1])
    while len(rest) > 0:
        a, b, c, d = rest.popleft()
        Nr = len(rest)
        A = [M]*N
        bi = [0]*N
        tmp = 0
        t = M-c
        r = A[a-1]-t
        if t >= 1 and r >= 0:
            for j in range(a):
                A[j] = t
            tmp += d
        bi[b-1] = -1
        bi[a-1] = 1
        for i in range(Nr):
            a, b, c, d = rest[i]
            t = A[b-1]-c
            r = A[a-1]-t
            if t >= 1 and r >= 0:
                if not (sum(bi[:a]) and r > 0):
                    bi[b-1] = -1
                    bi[a-1] = 1
                    for j in range(a):
                        A[j] -= r
                    tmp += d
        ans = max(tmp, ans)
    print(ans)
resolve()

Submission status: Wrong Answer

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


for i in range(1, M+1):
    
  for j in reversed(range(1, N)):
    X[j] += 1
    
    ans_1 = 0
    for k in S:
      if X[k[1]-1] - X[k[0]-1] == k[2]:
        ans_1 += k[3]
    if ans_1 > ans:
        ans = ans_1
      
print(ans)

Submission status: Wrong Answer

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

for _ in range(q):
    qlist.append(list(map(int,input().split())))

A = list(range(1,n+1))
flg = True
point = 0
currentpos = n-1
while(flg):
    pointtmp = 0
    for tmp in qlist:
        if A[tmp[1]-1] - A[tmp[0]-1] == tmp[2]:
            pointtmp += tmp[3]
    if pointtmp > point:
        point = pointtmp

    if A[currentpos] < m:
        A[currentpos] += 1
    elif currentpos > 0:
        currentpos -= 1
        A[currentpos] += 1
    else:
        flg = False

print(point)

Submission status: Wrong Answer

Solution code:
import itertools
N, M, Q = map(int, input().split())
A = []
for i in range(0, Q):
        a, b, c, d = map(int,input().split())
        A.append([a,b,c,d])

nums = []
for i in range(1, M+1):
        nums.append(i)

ans_l = [0]
for A_n in itertools.combinations(nums, N):
        ans = 0
        for i in range(0, Q):
                if((A_n[(A[i][1] - 1)] - A_n[(A[i][0] - 1)]) == A[i][2]):
                        ans += A[i][3]
        ans_l.append(ans)

print(max(ans_l))

Submission status: Wrong Answer

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions

t = stdin.readline().rstrip().split()
N = int(t[0])
M = int(t[1])
Q = int(t[2])

data = []
for el in range(Q):
    tt = stdin.readline().rstrip().split()
    a = int(tt[0])-1
    b = int(tt[1])-1
    c = int(tt[2])
    d = int(tt[3])
    data.append([a, b, c, d])

tes = 0
for pos in range(N):
    row = [1] * N
    res = 0
    check = False
    for el in data:
        if (row[el[1]] - row[el[0]]) == el[2]:
            continue
        else:
            if el[0] == pos:
                row[el[1]] = row[el[0]] + el[2]
            if el[1] == pos:
                row[el[0]] = row[el[1]] - el[2]
    for el in data:
        if (row[el[1]] - row[el[0]]) == el[2]:
            res += el[3]
    else:
        diffB = M - max(row)
        diffS = min(row)-1
        if min(row) + diffB >= 1 and diffB >= 0:
            check = True
        if max(row) - diffS <= M and diffS >= 0:
            check = True
        if res > tes and check:
            print(row)
            tes = res

print(tes)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, Q = map(int, input().split())
    R = [list(map(int, input().split())) for i in range(Q)]
    ARR = [0]*N
    SUM = 0
    ANS = 0
    for i in range(Q):
        if ARR[R[i][0]-1] != 0:
            A = ARR[R[i][0]-1] 
        else:
            ARR[R[i][0]-1] = 1 
            A = ARR[R[i][0]-1] 
        if ARR[R[i][1]-1] != 0:
            B = ARR[R[i][1]-1]
        else:
            ARR[R[i][1]-1] = ARR[R[i][0]-1] + R[i][2]
        if ARR[R[i][1]-1]-ARR[R[i][0]-1] == R[i][2]:
            SUM += R[i][3]
        if max(ARR) - min(ARR) <= M:
            ANS = max(ANS, SUM)
        SUM = 0
    print(ANS)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
l = list(input().split(" "))
m = [input().split(" ") for i in range(int(l[2]))]
m.sort()
print(m)
sum = int(m[0][3])
if int(m[0][2]) == 0:
    sum = 0
for i in range(1,int(l[2])):
    if int(m[i-1][0]) == int(m[i][0]):
        if int(m[i-1][2]) <= int(m[i][2]) and int(m[i][2]) != 0:
            sum = sum + int(m[i][3])
        else:
            sum = sum
            i += 1
    else:
        i += 1
print(int(sum))

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M,Q = [int(i) for i in input().split()]
A = []
for _ in range(Q):
    a,b,c,d = [int(i) for i in input().split()]
    A.append([a-1,b-1,c,d])

ans = 0

q = deque([list(range(N))])

while len(q) != 0:
    a = q.pop()
    s = 0
    for i in range(Q):
        if a[A[i][1]]-a[A[i][0]] == A[i][2]:
            s += A[i][3]
    ans = max([ans,s])
    for i in range(N-1):
        if a[i+1]-a[i] >0:
            b = a[:i]
            b.append(a[i]+1)
            b.extend(a[i+1:])
            q.appendleft(b)
    if a[N-1] < M-1:
        b = a[:N-1]
        b.append(a[N-1]+1)
        q.appendleft(b)

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

s = [1] * n
#st[b[i]] - st[a[i]]  = c[i]
num = n-1
#ans1 = [0] * 10000000
ans = 0
pre_ans = 0
t = 0

while(s[0] != m ):

    for i in range(q):
        if s[b[i]-1] - s[a[i]-1]  == c[i]:
            ans += d[i]
    #print(s)
    #print(ans)
    ans = max(pre_ans,ans)
    pre_ans = ans
    #t += 1

    ans = 0

    if s[num] < m:
        s[num] += 1
    elif num > 0 :
        num -= 1
        temp = s[num]+1
        if temp < m:
            for i in range(num,n):
                s[i] = temp
        else:
            while(s[num] == m):
                num -= 1
            temp = s[num]+1
            for i in range(num,n):
                s[i] = temp

        num = n-1

for i in range(q):
    if s[b[i]-1] - s[a[i]-1]  == c[i]:
        ans += d[i]

ans = max(pre_ans,ans)

print(pre_ans)

Submission status: Wrong Answer

Solution code:
from math import factorial as fact
import math
import sys
import itertools
import numpy as np
from collections import Counter
import datetime


#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def keta(N):
	return len(str(N))


def input_daytime(input_time):
	time,distance=input_time.split()
	t=time.split(":")
	se=str(t[-1]).split(".")
	dt1 = datetime.timedelta(hours=int(t[0]),minutes=int(t[1]),seconds=int(se[0]),milliseconds=int(se[1]))
	return dt1

def combinations(n,r):
	return list(itertools.combinations(range(n),r))



def all_sets(num_list):
	subsets=[]
	for i in range(2,len(num_list) + 1):
		for c in combinations(num_list, i):
			subsets.append(c) 
	return subsets

#公約数の列挙
def ch(x1):
	cf=[]
	for i in range(2,math.sqrt(x1)+1):
		if x1 % i==0:
			cf.append(i)
	return cf

def CountOneRoots(x,y):
	#x:縦，y:横
	return fact(x+y)/fact(x)/fact(y)

# 素因数分解
def factorization(n):
	tmp=n
	count=0
	for i in range(2,int(n**0.5)+2):
		if tmp%i==0:
			cnt=0
			while tmp%i==0:
				cnt+=1
				tmp//=i
			count+=1
	if tmp!=1:
		count+=1

	return count
			

def fl(a,b,x):
	b1=x//b
	x=math.floor(a*x/b)
	y=math.floor(b1)
	return x-y
	


n,m,q = input2()
abcd=[]
A=[m]*n
for i in range(q):
	abcd.append(input_array())
result=0
for row in abcd:
	result+=row[2]
print(result)
# a,b,n=input2()
# if b>n:
# 	b_ans=fl(a,b,n)
# 	# print(b_ans)
# else:
# 	b_ans=fl(a,b,b-1)

# for i in range(0,n,b):
# 	ans=fl(a,b,i)
# 	# print(ans)
# 	if ans> b_ans:
# 		b_ans=ans
# 	else:
# 		break
# # if i<n:
# # 	ans=fl(a,b,n)
# # 	if ans> b_ans:
# # 		b_ans=ans
# print(b_ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q = map(int,input().split())
a = [0 for i in range(n)]
q_list = []
for i in range(q):
    q_list.append(list(map(int,input().split())))

max_score = 0
for i in list(itertools.combinations(range(n+m),n)):
    tmp_max = 0
    for j in range(n):
        if j == 0:
            a[j] = i[j]
        else:
            a[j] = i[j]-i[j-1]-1
    for j in q_list:
        if a[j[1]-1] - a[j[0]-1] == j[2]:
            tmp_max += j[3]
    if tmp_max > max_score:
        max_score = tmp_max
print(max_score)

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

d=[[[0],0]]
for i in range(1,n):
  r=[[[],0]for i in range(m)]
  mk=0
  for j in d:
    for k in range(j[0][-1],m):
      s=0
      for a in l:
        if (i==a[1]-1)and(k-j[0][a[0]-1]==a[2]):
          s+=a[3]
      if r[k][1]<s+j[1]:
        r[k]=[j[0]+[k],s+j[1]]
  d=[]
  for rr in r:
    if len(rr[0]):
      d.append(rr)
print(max(list(map(lambda x:x[1],d+[[[],0]]))))

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:
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:
            if a < S[j,3]:
                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())

l = []

def inc(ary):
  s = ''
  ary[-1] += 1
  for i in range(len(ary)-1, 0, -1):
    v = ary[i]
    if v > (m - (n-1) + i):
      if i == 0:
        return False
      ary[i-1] += 1
      ary[i] = i+1
  return ary

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

a_tmp = [num for num in range(1, n+1)]
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
  if a_tmp[0] > (m-n+1):
    break
    
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 = 0
for i in range(1,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 sys
N,M,Q=map(int,input().split())
ABC=[]
ans=0
take=set([])
for i in range(Q):
  ABC+=[list(map(int,input().split()))]
ABC.sort(key=lambda x: x[3],reverse=True)
for i in range(Q):
  if len(take)==N:
    print(ans)
    sys.exit
  ans+=ABC[i][3]
  take.add(ABC[i][0])
  take.add(ABC[i][1])
  take=set(take)
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:
import itertools
import numpy as np

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

suretsu = np.array(range(1, M+1, 1))

com = list(itertools.combinations(suretsu,N))

num = 0
result = 0

for i in range(len(com)):
    num = 0
    for j in range(Q):
        a = listq[j][0]-1
        b = listq[j][1] - 1
        c =listq[j][2]
        if (com[i][b] - com[i][a] == c):
            num = num + listq[j][3]
    if (result < num):
        result = num
        # print(result)

print(result)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N,M,Ql = map(int, sys.stdin.readline().strip().split())
Q = []
for _ in range(Ql):
    Q.append(list(map(int, sys.stdin.readline().strip().split())))

max = 0
for A in itertools.combinations(range(1,M+1), N):
    ans = 0
    for Qi in Q:
        # print(A)
        # print(Qi)
        a,b,c,d = Qi

        if (A[b-1] - A[a-1]) == c:
            ans += d
        # print(ans)
    print()
    if max < ans:
        max = ans

print(max)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

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())
    
data = np.array(range(2, m, 1))
#nは組み合わせの総数
if (n - 2) * (n - 3) != 0:
    num = int(((m - 2) * (m - 3)) / ((n - 2) * (n - 3)))
else :
    num = 1
l = list(itertools.combinations(data, n - 2))
max = 0
for i in range(num):
    list_a = [1]+list(l[i])+[m]
    #list_a.append(m)
    sum = 0
    for j in range(q):
        #print(a[j], b[j], c[j])
        #print(list_a)
        if list_a[b[j]-1] - list_a[a[j]-1] == c[j]:
            sum += d[j]
    if sum > max:
        max = sum

print(max)

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, M):
        cans[1].add(i)

    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())
l=[list(map(int, input().split())) for i in range(q)]

score=sorted(l, key=lambda x: x[3],reverse=True)

A=[0]*(n+1)
ans=0

for i in range(q):
    a=l[i][0]
    b=l[i][1]
    c=l[i][2]
    d=l[i][3]
    if A[a]==0 and A[b]==0:
        A[a]=a
        A[b]=A[a]+c
        ans+=d

    elif A[a]==0 and A[b]!=0:
        A[a]=A[b]-c
        ans+=d

    elif A[a]!=0 and A[b]==0:
        A[b]=A[a]+c
        ans+=d

    elif A[b]-A[a]==c:
        ans+=d

print(ans)

Submission status: Wrong Answer

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

a = []
b = []
c = []
d = []

for i in range(Q):
    t_a, t_b, t_c, t_d = map(int, input().split())
    a.append(t_a - 1)
    b.append(t_b - 1)
    c.append(t_c)
    d.append(t_d)

A = [1] * N


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


res = point(A)

start = int("1" * N)
end = int("9" * N)

for i in range(start, end):
    res = max(res, point(list(str(i))))

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

d_sum_max=0

for i in  itertools.product(range(1,M+1), repeat=N):
    i = list(i)
    I=i.sort()
    if i == I:
        d_sum=0
        #print(i)
        for j in range(Q):
            if i[abcd[j][1]-1] - i[abcd[j][0]-1] == abcd[j][2]:
                d_sum += abcd[j][3]
            if d_sum_max < d_sum:
                d_sum_max = d_sum
        #print(d_sum)
print(d_sum_max)

Submission status: Wrong Answer

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

print('分かりません')

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
a = [0 for i in range(q)]
ans = 0
for i in range(q):
    a[i] = list(map(int,input().split()))
for f in range(1,11):
    for c in range(f,11):
        for k in range(c,11):
            for s in range(k,11):
                for p in range(s,11):
                    for l in range(p,11):
                        for e in range(l,11):
                            for u in range(e,11):
                                for v in range(u,11):
                                    b = [1,f,c,k,s,p,l,e,u,v]
                                    nn = 0
                                    for h in range(q):
                                        if b[a[h][1]-1] - b[a[h][0]-1] == a[h][2]:
                                            nn += a[h][3]
                                    ans = max(ans,nn)
print(ans)

Submission status: Wrong Answer

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

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

sA = sorted(A, key=lambda x:x[3], reverse=True)

ans = 0
for i in range(Q):
    cnt = 0
    num = 0
    tmp = [-1]*N
    tmp[sA[i][1]-1] = tmp[sA[i][0]-1]+sA[i][2]
    num += sA[i][3]
    cnt += 1
    for j in range(Q):
        if(cnt == N):
            break
        if(i == j):
            continue
        if(tmp[sA[j][1]-1] == -1):
            tmp[sA[j][1]-1] = tmp[sA[j][0]-1]+sA[j][2]
            num += sA[j][3]
            cnt += 1
        else:
            if(tmp[sA[j][1]-1] == tmp[sA[j][0]-1]+sA[j][2]):
                num += sA[j][3]
                cnt += 1
    ans = max(ans, num)            
print(ans)

Submission status: Wrong Answer

Solution code:

#長さN
#各値はM以下
n,m,q=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
tree = defaultdict(lambda: set([])) 
point = defaultdict(lambda: 0) 


for _ in range(q):
    a,b,c,d=map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
    point[(a-1,b-1)]=[c,d]
    point[(b-1,a-1)]=[-c,d]

group=[]
checked=[0]*n

#print(point)

i=0

while i<n:
    if checked[i]==0:
        checked[i]=1
        temp=[i]
        temp_group=[i]
        while temp!=[]:
            key=temp.pop()
            for item in tree[key]:
                if checked[item]==0:
                    checked[item]=1
                    temp.append(item)
                    temp_group.append(item)
        
        group.append(temp_group)
    i+=1

print(group)

result=0

for union in group:
    max_union_point=0
    for item in union:
        #itemが正しいと仮定する
        Ai=[0]*n
        Ai[item]=1
        temp=[item]
        union_point=0
        while temp!=[]:
            key=temp.pop()
            for item2 in tree[key]:
                if Ai[item2]==0:
                    
                    Ai[item2]=Ai[key]+point[(key,item2)][0]
                    union_point+=point[(key,item2)][1]
                else:
                    if Ai[item2]==Ai[key]-point[(key,item2)][0]:
                         union_point+=point[(key,item2)][1]
            max_union_point=max(max_union_point,union_point)
    result+=max_union_point

print(result)

Submission status: Wrong Answer

Solution code:
#C問題
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())

result = 0
A = [1] * N
for k in range(N):
    for i in range(2, M):
        A[N-1-k] = i
        temp = 0
        for j in range(Q):
            if(A[b[j]-1] - A[a[j]-1] == c[j]):
                    temp += d[j]
        if(temp > result):
            result = temp

print(result)

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

sA = sorted(A, key=lambda x:x[3], reverse=True)

ans = 0
for i in range(Q):
    cnt = 0
    num = 0
    tmp = [-1]*N
    tmp[sA[i][1]-1] = tmp[sA[i][0]-1]+sA[i][2]
    num += sA[i][3]
    cnt += 1
    for j in range(Q):
        if(cnt == N):
            break
        if(i == j):
            continue
        if(tmp[sA[j][1]-1] == -1):
            tmp[sA[j][1]-1] = tmp[sA[j][0]-1]+sA[j][2]
            num += sA[j][3]
            cnt += 1
        else:
            if(tmp[sA[j][1]-1] == tmp[sA[j][0]-1]+sA[j][2]):
                num += sA[j][3]
                cnt += 1
    print(tmp)
    ans = max(ans, num)            
print(ans)

Submission status: Wrong Answer

Solution code:
input = raw_input

#from copy import deepcopy

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

score_dict = {}

for i in range(1, n):
    for j in range(i+1, n+1):
        key = (i, j)
        score_dict[key] = []

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

#a_list = [{0} for i in range(n+1)]
a_list = [set() for i in range(n+1)]
a_list[1] = {0}

all_keys = [(i, cur) for cur in range(n+1) for i in range(1, cur)]
#used = {}
for key in all_keys:
    pairs = score_dict[key]
    i, j = key
    if len(pairs) == 0:
        continue

    #print(pairs)
    assert 1 <= i < j
    ais = a_list[i]
    ajs = a_list[j]
    #ais = deepcopy(a_list[i])
    #ajs = deepcopy(a_list[j])
    first = True
    for c, d in pairs:
        for ai in ais:
            aj = ai + c
            a_list[j].add(aj)
            first = False

        for aj in ajs:
            ai = aj - c
            if ai < 0:
                continue
            a_list[i].add(ai)
            first = False

        if first:
            a_list[j].add(c)



#print(a_list)

all_a_kumis = []

def f(last, last_i):
    if last_i == n:
        all_a_kumis.append(last)
        return

    cur_i = last_i+1
    if len(a_list[cur_i]) == 0:
        a_list[cur_i] = a_list[cur_i-1]
    for a in a_list[cur_i]:
        if last[-1] <= a:
            cur = last + [a]
            f(cur, cur_i)
        
f([0], 1)
#print(all_a_kumis)

out = 0
for cur_as in all_a_kumis:
    cur = 0
    for a, b, c, d in all_inputs:
        a -= 1
        b -= 1
        if cur_as[b] - cur_as[a] == c:
            cur += d
    out = max(out, cur)

print(out)



#last_end_ki = -1
#queues = []
#all_keys = [(i, cur) for cur in range(n+1) for i in range(1, cur)]
#
#last_end_ki = -1
#ki_dict = {}
#for cur in range(2, n+1):
#    start_ki = last_end_ki+1
#    end_ki = start_ki+cur-2
#    #cur_keys = all_keys[start_ki:end_ki+1]
#    ki_dict[cur] = [start_ki, end_ki]
#    last_end_ki += (cur-1)

Submission status: Wrong Answer

Solution code:
[n,m,q] = list(map(int,input().split(" ")))
a = []
for i in range (q):
    a.append(list(map(int,input().split(" "))))
ans = 0
for i in range (10**n):
    tmp = 0
    nlst = [1 for t in range(n)]
    for j in range (len(str(i))):
        nlst[j]=int(str(i)[j])+1
    if max(nlst)<=m and nlst==sorted(nlst):
        for k in range(q):
            a_ = a[k][0]
            b_ = a[k][1]
            c_ = a[k][2]
            d_ = a[k][3]
            if nlst[b_-1]-nlst[a_-1]==c_:
                tmp = tmp + d_
        if ans < tmp:
            ans = tmp
    
print(ans)

Submission status: Wrong Answer

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

# a,b,c,d = map(int, lQ[i].split())

high_score = 0

A = [1]*N
A[N-1] = M

while True:
    for i in reversed(range(1,N)):
        if A[i] < M:
            A[i] +=1
            break
    
    score = 0
    
    for j in range(Q):
        a,b,c,d = map(int, lQ[j].split())
        if A[b-1]-A[a-1]==c:
            score += d
    
    if score > high_score:
        high_score = score
        
    if A[1] == M:
        break;  

print(high_score)