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

    cans[1].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)
                    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:
nmq = input('')
n=int(nmq.split(' ')[0])
m=int(nmq.split(' ')[1])
q=int(nmq.split(' ')[2])

abcdlist=[]

for i in range(q):
    abcd=input('')
    abcdlist.append(abcd.split(' '))

mx=0

astr=''
for i in range(n):
    astr+='9'

for i in range(int(astr)):
    dx=0
    alist=[]
    for j in range(n):
        alist.append(int(str(i).zfill(n)[j])+1)
    for abcd in abcdlist:
        a=int(abcd[0])
        b=int(abcd[1])
        c=int(abcd[2])
        d=int(abcd[3])
        if alist[b-1]==alist[a-1]+c:
            dx+=d
    if dx > mx:
        mx=dx
print(mx)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

#BFS
q=deque()
q.append([1])

flag=True
while flag:
    fro=q.popleft()
    last=fro[-1]
    for to in range(last,M+1):
        temp=copy.deepcopy(fro)
        temp.append(to)
        if N<len(temp):
            flag=False
            break
        q.append(temp)

ans=float("-inf")
for L in q:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n,m,q = map(int, input().split())
tmp_A = [i+1 for i in range(m)]

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

top = 0    
for a in tmp_A:
    for b in [x for x in tmp_A if x >= a]:
        for c in [x for x in tmp_A if x >= b]:
            for d in [x for x in tmp_A if x >= c]:
                base = [a,b,c,d]
                res = 0
                for i in range(len(SU)):
                    e,f,g,h = SU[i][0], SU[i][1], SU[i][2], SU[i][3]
                    if e <= len(base) and f <= len(base):
                        if (base[f-1] - base[e-1]) == g:
                            res += h
                        if res >= top:
                            top = res         
print(top)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int ,input().split())
a = []
b = []
c = []
d = []
for i in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

ans = 0
for S in range(1<<(N+M)):
    if bin(S).count("1") != M:
        continue
    res = 0
    A = []
    pos = 1
    for i in range(N+M):
        if S & (1<<i):
            pos += 1
        else:
            A.append(pos)
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            res += d[i]
    if ans < res:
        ans = res

print(ans)

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:
s = list(map(int, input().split()))
n = s[0]
m = s[1]
q = s[2]

abcd = []

for i in range(q):
    inpu = list(map(int, input().split()))
    abcd.append(inpu)

maximum = 0

for i1 in range(1, 11):
    for i2 in range(i1, 11):
        for i3 in range(i2, 11):
            for i4 in range(i3, 11):
                for i5 in range(i4, 11):
                    for i6 in range(i5, 11):
                        for i7 in range(i6, 11):
                            for i8 in range(i7, 11):
                                for i9 in range(i8, 11):
                                    for i10 in range(i9, 11):
                                        iarray = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        goukei = 0
                                        for j in range(q):
                                            if iarray[abcd[j][1] - 1] - iarray[abcd[j][0] - 1] == abcd[j][2]:
                                                goukei = goukei + abcd[j][3]

                                        if goukei > maximum:
                                            maximum = goukei

print(maximum)

Submission status: Wrong Answer

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

ans = 0

ja = []
for i in range(q):
    ja.append(tuple(map(int, input().split())))

L = []

import itertools
lis = list(range(1,m+1))
for k in itertools.product(lis,repeat=n):
    score = 0
    for i in ja:
        if k[i[1]-1] - k[i[0]-1] == i[2]:
            score += i[3]
    ans = max(score,ans)

print(ans)

Submission status: Wrong Answer

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

def calc(L):
    s = 0
    for a, b, c, d in X:
        if L[b] - L[a] == c: s += d
    return s

def rec(L):
    if len(L) == N + 1:
        return calc(L)
    ma = 0
    for i in range(L[-1], M+1):
        ma = max(ma, rec(L + [i]))
    return ma

print(rec([0]))

Submission status: Wrong Answer

Solution code:
li=[]
ld=[]
k=0
ans=0
n,m,q=map(int,input().split())
A=[1]*n
for i in range(q):
    a,b,c,d=map(int,input().split())
    li.append([a,b,c])
    ld.append(d)
    if d>k:
        k=d
for i in range(q):
    dm=sorted(ld,reverse=True)[i]
    lia=li[ld.index(dm)]
    if A[lia[1]-1]==1:
        A[lia[1]-1]=A[lia[1]-lia[0]-1]+lia[2]
        ans+=dm
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    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 i in range(Q):
        a[i], b[i], c[i], d[i] = map(int, input().split())

    seq = [i for i in range(1, 11)]

    max_point = 0

    for e in list(itertools.combinations_with_replacement(seq, N)):
        point = 0
        for i in range(Q):
            if e[b[i]-1] - e[a[i]-1] == c[i]:
                point += d[i]
        if point >= max_point:
            max_point = point

    print(max_point)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 間違えてるのはわかってる
N, M, Q = map( int, input().split() )

point_list = []
for i in range( Q ):
  a, b, c, d = map( int, input().split())
  point_list.append( [ a, b, c, d ] )
  
l = ['{0:04b}'.format(i) for i in range( 2 ** M ) if sum(list(map(int, '{0:04b}'.format(i)))) == N]

def bin_to_numlist( bin ):
  l = []
  cnt = 1
  for i in list(map(int, bin)):
    if i == 1:
      l.append( cnt )
    cnt += 1
  return l

target = map( bin_to_numlist, l )
max_point = 0
for t in target:
  point = 0
  for a, b, c, d in point_list:
    if t[ b - 1 ] - t[ a - 1 ] == c:
      point += d
  max_point = max( max_point, point )
  print( t, point )
print( max_point )

Submission status: Wrong Answer

Solution code:
import itertools

N, M, Q = input().split()
S = [input().split() for i in range(int(Q))]


ran = range(int(M))
pattern = []
res = 0
for pair in itertools.combinations_with_replacement(ran, int(M)):
    pattern.append(pair)


for p in pattern:
    point = 0

    for s in S:

        if int(s[1]) > len(p) or int(s[0]) > len(p):
            pass
        elif p[int(s[1])-1] - p[int(s[0])-1] == int(s[2]):
            point += int(s[3])
    if point > res:
        res = point
print(str(res))

Submission status: Wrong Answer

Solution code:
[n,m,q]=list(map(int,input().split()))
chokudai=[]
maxpoint=0
for i in range(q):
    chokudai.append(list(map(int,input().split())))
for i in range(int(pow(m,n))):
    numlist=[]
    point=0
    for j in range(n):
        numlist.append(i//m**(n-1-j))
        i=i%m**(n-1-j)
    for j in range(q):
        if numlist[chokudai[j][1]-1]-numlist[chokudai[j][0]-1]==chokudai[j][2]:
            point+=chokudai[j][3]
    if maxpoint<point:
        maxpoint=point

print(maxpoint)

Submission status: Wrong Answer

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

data = [[0] * 4] * q

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

dataSort = sorted(data)

aFirst = data[0][0]
bFirst = data[0][1]
cf = data[0][2]
df = data[0][3]
ans = df

for i in range(1, q):
    aa = data[i][0]
    bb = data[i][0]
    if (aa == aFirst):
        if (bb == bFirst):
            if (df >= data[i][3]):
                pass
            else:
                ans -= df
                ans += data[i][3]
        else:
            ans += data[i][3]
    else:
        if (data[i][1] > bFirst):
            pass
        else:
            if (data[i][2] > cf):
                ans += data[i][3]
    aFirst = aa
    bFirst = bb
    cf = data[i][2]
    df = data[i][3]

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n, m, q = [int(i) for i in input().split()]
qs = []
for _ in range(q):
    qs.append([int(i) for i in input().split()])

cmb = []
for i in range(1, m):
    cmb += [i] * n

comb = list(combinations(cmb, n))

finalTotal = 0
for arrA in comb:
    total = 0
    for arrQ in qs:
        if arrA[arrQ[1]-1] - arrA[arrQ[0]-1] == arrQ[2]:
            total += arrQ[3]
    finalTotal = max(finalTotal, total)
print(finalTotal)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m,q = map(int,input().split())
l = list(list(map(int,input().split())) for _ in range(q))
if m<7:
  num = ["1"*n]
  k = deque(["1"*n])
  while len(k)!=0:
    h = k.popleft()
    if int(h[-1])<m:
      num.append(str(int(h)+1))
      num.append(str(int(h)+11))
      num.append(str(int(h)+111))
      k.append(str(int(h)+1))
      k.append(str(int(h)+11))
      k.append(str(int(h)+111))
  num = list(set(num))
  ma = 0
  for i in num:
    s = 0
    for a,b,c,d in l:
      if int(i[b-1])-int(i[a-1])==c:
        s += d
        ma = max(ma,s)
  print(ma)
else:
  l1 = sorted(l,key=lambda x:x[3])[::-1]
  print(l1[0][-1])

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
    if A[1] == M:
        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

print(high_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):
    #print(A)
    #点数計算
    wa = 0
    for i in range(Q):
        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:
import numpy as np
import math

N, M, Q = (int(x) for x in input().split())
S = np.array([list(map(int,input().split(" "))) for i in range(Q)])
sum = np.zeros(M)
a = 0
k = 0

for i in range(M):
    for j in range(Q):
        if S[j,2] == i:
            if a < S[j,3]:
                a = S[j,3]
        sum[k] = a
    k += 1

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

Submission status: Wrong Answer

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

def calc(L):
    s = 0
    for a, b, c, d in X:
        if L[b] - L[a] == c: s += d
    return s

def rec(L):
    if len(L) == N + 1:
        return calc(L)
    ma = 0
    for i in range(L[-1], N+1):
        ma = max(ma, rec(L + [i]))
    return ma

print(rec([0]))

Submission status: Wrong Answer

Solution code:
def main():
    import copy
    n,m,q=map(int,input().split())
    a=[]
    b=[]
    c=[]
    d=[]
    ans=0
    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)
    indices = [*range(q)]
    sorted_indices = sorted(indices, key=lambda i: -d[i])
    sorted_num = [d[i] for i in sorted_indices]
    A=[1]*(n+1)
    for i in range(q):
        A[b[i]-1]=c[i]+A[a[i]-1]
    times=0
    for i in sorted_indices:
        #A[b[i]]-A[a[i]]=c[i]→A[b[i]=c[i]+A[a[i]]
        pre=copy.copy(A)
        A[b[i]-1]=c[i]+A[a[i]-1]
        if A[b[i]]>m:
            break
        
        #All Check
        times+=1
        for j in range(1,n+1):
            if A[j]<A[j-1]:
                for k in range(times):
                    si=sorted_indices[k]
                    A[b[si]-1]=c[si]+A[a[si]-1]
        tmp=0
        for j in range(q):
            if A[b[j]-1]-A[a[j]-1]==c[j]:
                tmp+=d[j]
        
        if ans>tmp:
            A=copy.copy(pre)
        ans=max(ans,tmp)
        
    print(ans)
    
    

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

N, M, Q = input().split()
S = [input().split() for i in range(int(Q))]
print(S)

ran = range(int(M))
pattern = []
res = 0
for pair in itertools.combinations_with_replacement(ran, int(M)):
    pattern.append(pair)
print(pattern)

for p in pattern:
    point = 0
    print(p)
    for s in S:
        print(p)
        if int(s[1]) > len(p) or int(s[0]) > len(p):
            pass
        elif p[int(s[1])-1] - p[int(s[0])-1] == int(s[2]):
            point += int(s[3])
    if point > res:
        res = point
print(str(res))

Submission status: Wrong Answer

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

M = [int(i) for i in range(1, M+1)]
A_possible = list(itertools.combinations(M, N))
A_score = 0
for A in A_possible:
    A_sum = 0
    for i in range(Q):
        A_test = A[a_b_c_d[i][1]-1] - A[a_b_c_d[i][0]-1]
        if A_test == a_b_c_d[i][2]:
            A_sum += a_b_c_d[i][3]
    if A_score < A_sum:
        A_score = A_sum
print(A_score)

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(q):
    x1, x2, x3, x4 = map(int, input().split())
    a.append(x1)
    b.append(x2)
    c.append(x3)
    d.append(x4)

print(sum(d) - min(d))

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for i in range(Q)]
ABCD.sort(key=lambda x: x[3])
A = [1 for _ in range(N)]
for i in range(Q):
    if not(A[ABCD[i][0]-1] + ABCD[i][2] > M):
        A[ABCD[i][1]-1] = A[ABCD[i][0]-1] + ABCD[i][2]

ans = 0
for i in range(Q):
    if A[ABCD[i][1]-1] == A[ABCD[i][0]-1] + ABCD[i][2]:
        ans += ABCD[i][3]
print(ans)

Submission status: Wrong Answer

Solution code:
data = input().split()
from itertools import product
n = int(data[0])
m = int(data[1])
q = int(data[2])

a = []
b = []
c = []
d = []
for i in range(q):
    data2 = input().split()
    a.append(int(data2[0]))
    b.append(int(data2[1]))
    c.append(int(data2[2]))
    d.append(int(data2[3]))

array = []
max = 0

A = []
for i in range(1,m+1):
    A.append(i)
A = tuple(A)
for array in product(A, repeat=n):
    temp = 0
    for i_q in range(q):
        #print(b[i_q], a[i_q])
        if array[b[i_q]-1] - array[a[i_q]-1] ==  c[i_q]:
            temp += d[i_q]
    if max < temp:
        max = temp
print(max)

Submission status: Wrong Answer

Solution code:
li = list(map(int, input().split()))
lists = []
for a in range(li[2]):
    lists.append(list(map(int, input().split())))
listA = []
for i in range(1, li[0] + 1):
    if i > li[1]:
        listA.append(li[1])
    else:
        listA.append(i)
totals = []
for i in range(li[2]):
    ai = lists[i][0]-1
    bi = lists[i][1]-1
    ci = lists[i][2]
    di = lists[i][3]
    total = 0
    if not listA[bi] - listA[ai] == ci:
        listA[bi] = listA[ai] + ci
    for j in range(li[2]):
        if listA[lists[j][1]-1] - listA[lists[j][0]-1] == lists[j][2]:
            total = total + lists[j][3]   
        elif listA[lists[j][0]-1]+lists[j][2]<listA[lists[j][0]]:
          listA[lists[j][1]-1]=listA[lists[j][0]-1]+lists[j][2]
          total=total+lists[j][3]
    totals.append(total)
print(max(totals))

Submission status: Wrong Answer

Solution code:
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 
    n,m,q = map(int,input().strip().split())
    abcd = []
    for i in range(q):
        # a,bはindexの次元，cは値， dはポイント
        temp_a,temp_b,temp_c,temp_d = map(int,input().strip().split())
        abcd.append((temp_a - 1, temp_b - 1, temp_c, temp_d ))

    # 
    eprint('n,m,q ',end=':\n')
    eprint(n,m,q)
    eprint('abcd ',end=':\n')
    eprint(abcd)

    #
    ans=0
    l=[i for i in range(1,m+1)]
    ll=[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]+[i for i in range(1,m+1)]
    for A in itertools.combinations(ll,n):
        #
        eprint('A ',end=':\n')
        eprint(A)

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools as itr
N,M,Q = map(int,input().split())
sheat = list()
for i in range(Q):
    sheat.append(list(map(int,input().split())))

comb = tuple(itr.combinations(range(1,M+1),N))
Maxsum = 0
# print(sheat)
# print(comb)
sumd = 0
for i in range(len(comb)):
    ansum = 0
    for j in range(Q):
        if(comb[i][sheat[j][1]-1]-comb[i][sheat[j][0]-1] == sheat[j][2]):
            ansum += sheat[j][3]
           
    if(Maxsum < ansum):
        Maxsum = ansum
    # print(ansum)
print(Maxsum)      
# for i in range(Q):
#     sumd += sheat[i][3]
# print(sumd)
#nCm

#A_1,A_2,A_3,...A_n,M
#A_b-i - A_a-i = C_i  :Sum di

# A= {1,3,4} :comb          ↓sheat
#  i = 1:4 - 1 = 3o 100     [1,3,3]
#      2:3 - 1 = 2o  10     [1,2,2]
#      3:4 - 3 = 1*  10     [2,3,2]
#                   110

Submission status: Wrong Answer

Solution code:
from sys import stdin


# 重み付きUnion-Find木
class Weighted_Union_Find():
    def __init__(self, N=1, SUM_UNITY=0):
        self.par  = [i for i in range(N)]  # 親ノード
        self.rank = [0] * N                # ランク
        self.diff_weight = [SUM_UNITY] * N 
    
    # 経路圧縮
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.root(self.par[x])
            self.diff_weight[x] = self.diff_weight[self.par[x]]
            self.par[x] = r
            return r

    # 経路圧縮＋重みを返す
    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    # xとyが同じグループに属するか判定
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # xとyの属するグループを1つにまとめる
    def merge(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: 
            return False
        else:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
                w = -w
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.diff_weight[y] = w
            return True

    # xとyが同じグループにいるとき、xとyの重みの差を返す
    def diff(self,x,y):
        return self.weight(y) - self.weight(x)# 最小化問題
        

class DFS():
    def __init__(self):
        self.cost = 0

    def dfs(self,req,wuf,cnt):
        if req == []:
            if cnt > self.cost:
                self.cost = cnt
            return
        else:
            a,b,c,d = req[0]
            a -= 1
            b -= 1
            if wuf.issame(a,b):
                diff = wuf.diff(a,b)
                if diff == c:
                    cnt += d
                self.dfs(req[1:],wuf,cnt)
            else:
                wuf.merge(a,b,c)
                cnt += d
                #if a+1 != b:
                #    if max(wuf.diff_weight[a+1:b])-wuf.diff_weight[a]<c:

                self.dfs(req[1:],wuf,cnt)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M, Q = list(map(int,_in[0].split(' ')))  # type:list(int)
    a_b_c_d_arr = []
    for i in range(Q):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        a_b_c_d_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    #A_iter = [0]*(M+1)]
    wuf = Weighted_Union_Find(N)
    dfs_class = DFS()
    dfs_class.dfs(a_b_c_d_arr, wuf, cnt=0)
    cnt = dfs_class.cost
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Wrong Answer

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

for i in range(1, M + 1):
    if M == 1: break
    for j in range(i, M + 1):
        if M == 2: break
        for k in range(j, M + 1):
            if M == 3: break
            for l in range(k, M + 1):
                if M == 4: break
                for m in range(l, M + 1):
                    if M == 5: break
                    for n in range(m, M + 1):
                        if M == 6: break
                        for o in range(n, M + 1):
                            if M == 7: break
                            for p in range(o, M + 1):
                                if M == 8: break
                                for q in range(p, M + 1):
                                    if M == 9: break
                                    for r in range(q, M + 1):
                                        if M == 10: break

print(1)

Submission status: Wrong Answer

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

ans_point = 0
for i in range(q):
    # どれかを正しいとする
    c_a, c_b, c_c = values[i][0], values[i][1], values[i][2]
    ans = [1] * (n + 1)
    ans[c_b] = ans[c_a] + c_c
    for a, b, c, d in values:
        temp = ans[b]
        ans[b] = ans[a] + c
        if ans[c_b] - ans[c_a] != c_c or ans[b] >= m:
            ans[b] = temp
    point = 0
    for a, b, c, d in values:
        if ans[b] - ans[a] == c:
            point += d
    ans_point = max(ans_point, point)

print(ans_point)

Submission status: Wrong Answer

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

H=[[0]]*Q
i=0
while i<Q:
    H[i]=list(map(int,input().split()))[::-1]
    i+=1
H=sorted(H)[::-1]
A=[0]+[1]*N

ans=0
for d,c,b,a in H:
    if A[b]<=c+A[a]<=M:
        ans+=d
        zouka=c+A[a]-A[b]
        j=a+1
        while j<=N:
            A[j]+=zouka
            j+=1
    print(A)

print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for i in range(Q)]
ABCD.sort(key=lambda x: x[3], reverse=True)
A = [1 for _ in range(N)]
for i in range(Q):
    if not(A[ABCD[i][0]-1] + ABCD[i][2] > M):
        A[ABCD[i][1]-1] = A[ABCD[i][0]-1] + ABCD[i][2]

ans = 0
for i in range(Q):
    if A[ABCD[i][1]-1] == A[ABCD[i][0]-1] + ABCD[i][2]:
        ans += ABCD[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)]

def f(nums):
  out=0
  for samp in abcd:
    if nums[samp[1]-1]-nums[samp[0]-1]==samp[2]:
      out+=samp[3]
  return out

def g(nums):
  if nums[-1]<M:
    nums[-1]+=1
    return nums, False
  
  i=N-1
  while i>=0 and nums[i]==M:
    i-=1
  if i<0:
    return None, True
  
  nums=nums[:i]+[nums[i]+1 for _ in range(N-i)]
  return nums, False

nums=[1]*N
fi=False
ans=0

while fi==False:
  p=f(nums)
  if ans<p:
    ans=p
  print(nums)
  nums, fi=g(nums)
  
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
A = [list(map(int,input().split())) for i in range(Q)]
cnt_all = [ ]
for i in range(M):
  cnt = 0
  for j in range(Q):
    if 0 < (M-i)-A[j][2] == A[j][2] and M-i <= A[j][2]:
      cnt += A[j][3]
  cnt_all.append(cnt)
print(max(cnt_all))

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

    ans1[t] = 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






print(max(ans1))