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:
def solve(arr, abcd, Q):
    ans = 0
    for i in range(Q):
        if arr[abcd[i][1]-1]-arr[abcd[i][0]-1] == abcd[i][2]:
            ans += abcd[i][3]
    return ans


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

ans = 0
for i1 in range(1, M+1):
    for i2 in range(2, M+1):
        if i1 > i2:
            continue

        for i3 in range(3, M+1):
            if i2 > i3:
                continue
            if N == 3:
                tmp = [i1, i2, i3]
                tmp_ans = solve(tmp, abcd, Q)
                ans = max(tmp_ans, ans)

            for i4 in range(4, M+1):
                if i3 > i4:
                    continue
                if N == 4:
                    tmp = [i1, i2, i3, i4]
                    tmp_ans = solve(tmp, abcd, Q)
                    ans = max(tmp_ans, ans)

                for i5 in range(5, M+1):
                    if i4 > i5:
                        continue
                    if N == 5:
                        tmp = [i1, i2, i3, i4, i5]
                        tmp_ans = solve(tmp, abcd, Q)
                        ans = max(tmp_ans, ans)

                    for i6 in range(6, M+1):
                        if i5 > i6:
                            continue
                        if N == 6:
                            tmp = [i1, i2, i3, i4, i5, i6]
                            tmp_ans = solve(tmp, abcd, Q)
                            ans = max(tmp_ans, ans)

                        for i7 in range(7, M+1):
                            if i6 > i7:
                                continue
                            if N == 7:
                                tmp = [i1, i2, i3, i4, i5, i6, i7]
                                tmp_ans = solve(tmp, abcd, Q)
                                ans = max(tmp_ans, ans)

                            for i8 in range(8, M+1):
                                if i7 > i8:
                                    continue
                                if N == 8:
                                    tmp = [i1, i2, i3, i4, i5, i6, i7, i8]
                                    tmp_ans = solve(tmp, abcd, Q)
                                    ans = max(tmp_ans, ans)

                                for i9 in range(9, M+1):
                                    if i8 > i9:
                                        continue
                                    if N == 9:
                                        tmp = [i1, i2, i3, i4,
                                               i5, i6, i7, i8, i9]
                                        tmp_ans = solve(tmp, abcd, Q)
                                        ans = max(tmp_ans, ans)

                                    for i10 in range(10, M+1):
                                        if i9 > i10:
                                            continue
                                        if N == 10:
                                            tmp = [i1, i2, i3, i4,
                                                   i5, i6, i7, i8, i9, i10]
                                            tmp_ans = solve(tmp, abcd, Q)
                                            ans = max(tmp_ans, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
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,B,C,D=map(int,input().split())
    a[i]=A;b[i]=B;c[i]=C;d[i]=D
r=[]
def dfs(i,depth,b,h):
    if depth==0:
        b.append(h)
        return
    for j in range(i,M):
        nh=h[:]
        nh.append(j)
        dfs(j,depth-1,b,nh)
dfs(1,10,r,[])
ans=0
for R in r:
    cnt=0
    for j in range(Q):
        if R[b[j]-1]-R[a[j]-1]==c[j]:
            cnt+=d[j]
    ans=max(cnt,ans)
print(ans)

Submission status: Wrong Answer

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

def gen(mae):
    global A_cand
    if len(mae)==N:
        A_cand.append(mae)
        return 0
    for one in range(mae[-1], 11):
        gen(mae+[one])
for i in range(1,M+1):
    gen([i])
for one in A_cand:
    score = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if one[b-1]-one[a-1]==c:
            score+=d
    max_score = max(score, max_score)
print(max_score)

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 = [0 for _ in range(N)]
for i in range(Q):
    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 = [int(n) for n in 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] = [int(n) for n in input().split()]

def gen(i, n, m):
    if n == 0:
        yield []
        return
    for f in range(i, m - n + 2):
        for rest in gen(f, n - 1, m):
            yield [f] + rest

sm = 0
for A in gen(1,N,M):
    s = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    if s > sm:
        sm = s

print(sm)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
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,B,C,D=map(int,input().split())
    a[i]=A;b[i]=B;c[i]=C;d[i]=D
r=[]
def dfs(i,depth,b,h):
    if depth==0:
        b.append(h)
        return
    for j in range(i,11):
        nh=h[:]
        nh.append(j)
        dfs(j,depth-1,b,nh)
dfs(1,10,r,[])
ans=0
for R in r:
    cnt=0
    for j in range(Q):
        if R[b[j]-1]-R[a[j]-1]==c[j]:
            cnt+=d[j]
    ans=max(cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
de = deque()
n,m,q = map(int,input().split())
queries = []
for i in range(q):
    a,b,c,d = map(int,input().split())
    queries.append((a,b,c,d))
de.append([1])
maxscore = 0
while de: 
    li = de.popleft()
    if len(li) < n:
        for i in range(li[-1],11):
            new_li = li + [i]
            de.append(new_li)
    else:
        score = 0
        for i in range(q):
            a,b,c,d = queries[i]
            if li[b-1]-li[a-1] == c:
                score += d
        maxscore = max(maxscore,score)
print(maxscore)

Submission status: Wrong Answer

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

def count(a):
    score = 0
    for i in range(q):
        if a[l[i][1]-1] - a[l[i][0]-1] == l[i][2]:
            score += l[i][3]
    return score

def dfs(x,now,s):
    if x == n:
        return count(s)
    score = 0
    for i in range(now,m+1):
        s.append(i)
        score = max(score,dfs(x+1,i,s))
        s.pop()
    return score
print(dfs(0,0,[]))

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
A=[]
ans=[M]*N
ischecked=[0]*N
point=0
for i in range(Q):
    a,b,c,d=map(int,input().split())
    A.append((d,a,b,c))
A.sort(reverse=True)
for d,a,b,c in A:
    if ischecked[b-1]==1 and ischecked[a-1]==1:
        continue
    elif ischecked[a-1]==0 and ischecked[b-1]==1:
        ans[a-1]=ans[b-1]-c
        point+=d
        ischecked[a-1]=1
    elif ischecked[a-1]==1 and ischecked[b-1]==0:
        if ans[a-1]+c<=M:
            ans[b-1]=ans[a-1]+c
            point+=d
            ischecked[b-1]=1
    else:
        ischecked[a-1]=1
        ischecked[b-1]=1
        ans[a-1]=ans[b-1]-c
        point+=d
print(point)

Submission status: Wrong Answer

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

def gen(mae):
    global A_cand
    if len(mae)==N:
        A_cand.append(mae)
        return 0
    for one in range(mae[-1], 11):
        gen(mae+[one])
for i in range(1,11):
    gen([i])

for one in A_cand:
    score = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if one[b-1]-one[a-1]==c:
            score+=d
    max_score = max(score, max_score)
print(max_score)

Submission status: Wrong Answer

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


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

    from itertools import combinations_with_replacement
    answer = 0
    for AA in combinations_with_replacement(range(0,M+1),r=N):
        tmp_ans = 0
        for q in range(Q):
            if AA[b[q]-1] - AA[a[q]-1] ==  c[q]:
                tmp_ans += d[q]
  
        answer = max(answer,tmp_ans)
    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
nums=[]
for i in range(Q):
  nums.append(list(map(int,input().split())))
ans=0
bit=[1]*N

for n in range(N):
  n=(-1)*(n+1)
  for m in range(M-1):
    tmp=0
    for num in nums:
      if bit[num[1]-1]-bit[num[0]-1]==num[2]:
        tmp+=num[3]
    if tmp>ans:
      ans=tmp
    bit[n]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i1 in range(1,m+1):
  for i2 in range(i1,m+1):
    for i3 in range(i2,m+1):
      for i4 in range(i3,m+1):
        for i5 in range(i4,m+1):
          for i6 in range(i5,m+1):
            for i7 in range(i6,m+1):
              for i8 in range(i7,m+1):
                for i9 in range(i8,m+1):
                  for i10 in range(i9,m+1):
                    tmp=0
                    arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b]-arrs[1]==c:
                        tmp+=d
                    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations_with_replacement
def input(): return sys.stdin.readline().strip()


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

    if N > M:
        print(0)
        return

    LIST = [i for i in range(1, M + 1)]
    ans = 0
    for A in list(combinations_with_replacement(LIST, N)):
        val = 0
        for a, b, c, d in pair:
            if A[b] - A[a] == c:
                val += d
        ans = max(ans, val)
        #print("val={}, A={}".format(val, A))
    print(ans)



    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
a, b, c, d = [[0]*q for i in range(4)]
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

def dfs(vec, mx, cnt):
    if cnt:
        tmp = 0
        for i in range(mx, m+1):
           tmp = max(tmp, dfs(vec+[i], i, cnt-1))
        return tmp
    else:
        tmp = 0
        for i in range(q):
            if vec[b[i]]-vec[a[i]]==c[i]: tmp += d[i]
        return tmp
print(dfs([], 0, n))

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

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

query = tuple(tuple(map(int, input().split())) for _ in range(Q))

ans = 0
for comb in combinations_with_replacement(range(1, 11), N):
    score = 0
    for a, b, c, d in query:
        if comb[b-1] - comb[a-1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]
L=[]
for i in range(1,11):
  for i2 in range(i,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):
                    L.append((i,i2,i3,i4,i5,i6,i7,i8,i9,i10))
ans=[]
for i in range(len(L)):
  ct=0
  for j in range(q):
    if L[i][l[j][1]-1]-L[i][l[j][0]-1]==l[j][2]:
      ct+=l[j][3]
  ans.append(ct)
print(max(ans))

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # import math
    input = stdin.readline

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

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

    # print(abcd)
    ans = 0

    for a in range(1,11):
        for b in range(a,11):
            for c in range(b,11):
                for d in range(c,11):
                    for e in range(d,11):
                        for f in range(e,11):
                            for g in range(f,11):
                                for h in range(g,11):
                                    for i in range(h,11):
                                        for j in range(i,11):
                                            num = [a, b, c, d, e, f, g, h, i, j]
                                            num_sum = 0
                                            for k, l, m, n in abcd:
                                                if num[l]-num[k] == m:
                                                    num_sum += n
                                            # print(num_sum)
                                            if num_sum > ans:
                                                ans = num_sum
    print(ans)

Submission status: Wrong Answer

Solution code:
def sol(case):
    A = [1 for _ in range(N)]
    used = [False for _ in range(N)]
    ans = 0
    for i, flag in enumerate(case):
        if flag == '1':
            a, b, c, d = B[i]
            a -= 1
            b -= 1
            if A[b] - A[a] == c:
                used[a] = True
                used[b] = True
                ans += d
            else:
                if used[b] is False and A[a] + c <= M:
                    A[b] = A[a] + c
                    used[a] = True
                    used[b] = True
                    ans += d
                else:
                    return -1
        else:
            continue
    return ans


if __name__ == '__main__':
    N, M, Q = map(int, input().split())
    B = [list(map(int, input().split())) for _ in range(Q)]

    ans = 0
    for i in range(2 ** Q):
        case = bin(i)[2:].zfill(Q)
        res = sol(case)
        if res != -1 and res in [357500, 450067]:
            print(case, res)
        if res >= 0:
            ans = max(ans, res)

    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
N, M, Q = [int(x) for x in input().split()]
lst = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for seq in combinations_with_replacement(range(1, M+1), N):
    print(seq)
    tmp = 0
    for a, b, c, d in lst:
        if (seq[b-1] - seq[a-1] == c):
            tmp += d
    ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
ans = 0
lis = [list(map(int,input().split())) for i in range(q)]
lis.sort(key=lambda x:x[1])
for i in range(2 ** q):
    s = str(format(i,"b").zfill(q))
    num = [-1 for i in range(n)]
    num[0] = 1
    score = 0
    for j in range(q):
        if s[j] == "1":
            if num[lis[j][1]-1] == -1 or num[lis[j][1]-1] == num[lis[j][0]-1] + lis[j][2]:
                num[lis[j][1]-1] = num[lis[j][0]-1] + lis[j][2]
                score += lis[j][3]
            else:
                break
    for j in range(n-1):
        if num[j] == -1:
            num[j] = num[j-1]
    for j in range(n-1):
        if num[j] > num[j+1]:
            break
    if num[-1] <= m:
        ans = max(ans,score)
print(ans)

Submission status: Wrong Answer

Solution code:
import os
from functools import reduce
from operator import mul

import itertools
import sys

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def ncr(n, r, mod=None):
    """
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    # 何度も呼ぶ場合は combination.py をつかう
    r = min(n - r, r)
    if r == 0:
        return 1
    if mod:
        return reduce(mul, range(n, n - r, -1)) * mod_inv(reduce(mul, range(r, 0, -1)), mod) % mod
    else:
        # math.factorial よりこっちのが速い
        # https://atcoder.jp/contests/abc110/submissions?f.Task=&f.Language=&f.Status=&f.User=nohtaray
        return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


def nhr(n, r, mod=None):
    """
    重複組み合わせの総数 nHr
    :param int n:
    :param int r:
    :param int mod:
    """
    return ncr(n + r - 1, r, mod)


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


# a = nhr(10, 10)
N, M, Q = list(map(int, sys.stdin.buffer.readline().split()))
ABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

ans = 0
for r in range(N + 1):
    for idx in itertools.combinations_with_replacement(range(1,N+ 1), r=r):
        a = [0] * (N + 10)
        a[1] = 1
        for i in idx:
            a[i] += 1
        cum = cumsum(a)
        pt = 0
        for a, b, c, d in ABCD:
            if cum[b] - cum[a] == c:
                pt += d
        ans = max(ans, pt)
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)]

import itertools

tmp = []
for i in range(1,M+1):
    tmp.append(i)
    
A = list(itertools.combinations(tmp,N))


answer = 0

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

Submission status: Wrong Answer

Solution code:
n,m,q=map(int, input().split())
abcd=[list(map(int, input().split())) for i in range(q)]
from itertools import combinations_with_replacement
data=list(range(1,11))
prep=combinations_with_replacement(data, n)
ans=0
for p in prep:
    tmp=0
    p=sorted(list(p))
    for i in range(q):
        if p[abcd[i][1]-1]-p[abcd[i][0]-1]==abcd[i][2]:
            tmp+=abcd[i][3]
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def calc(l):
    tmp = 0
    for Q in Qs:
        if l[Q[1] - 1] - l[Q[0] - 1] == Q[2]:
            tmp += Q[3]
    return tmp


def solve(l, d):
    global n
    global ans
    if d == n:
        ans = max(ans, calc(l))
        return
    if l[-1] == m:
        return
    for i in range(l[-1], m + 1):
        l_ = l + [i]
        solve(l_, d + 1)


n, m, q = map(int, input().split())
Qs = [list(map(int, input().split())) for _ in range(q)]
ans = 0
solve([1], 1)
print(ans)

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,M,Q = Ints()
List = []

for i in range(Q):
    a,b,c,d = Ints()
    List.append([a,b,c,d])
    
import itertools
Num = [i for i in range(N+M)]
Ans = 0

for i in itertools.combinations(Num, N):
    TMP = []
    now = 1
    pre = -1
    for j in i:
        TMP.append(now+j-pre-1)
        now = now+j-pre-1
        pre = j
    #print(TMP)
    
    Tensuu = 0
    for (a,b,c,d) in List:
        if TMP[b-1]-TMP[a-1] == c:
            Tensuu += d
    Ans = max(Ans, Tensuu)
print(Ans)

Submission status: Wrong Answer

Solution code:
import os
from functools import reduce
from operator import mul

import itertools
import sys

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def ncr(n, r, mod=None):
    """
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    # 何度も呼ぶ場合は combination.py をつかう
    r = min(n - r, r)
    if r == 0:
        return 1
    if mod:
        return reduce(mul, range(n, n - r, -1)) * mod_inv(reduce(mul, range(r, 0, -1)), mod) % mod
    else:
        # math.factorial よりこっちのが速い
        # https://atcoder.jp/contests/abc110/submissions?f.Task=&f.Language=&f.Status=&f.User=nohtaray
        return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


def nhr(n, r, mod=None):
    """
    重複組み合わせの総数 nHr
    :param int n:
    :param int r:
    :param int mod:
    """
    return ncr(n + r - 1, r, mod)


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


# a = nhr(10, 10)
N, M, Q = list(map(int, sys.stdin.buffer.readline().split()))
ABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

ans = 0
for r in range(N + 1):
    for idx in itertools.combinations_with_replacement(range(2, M + 1), r=r):
        a = [0] * (N + 10)
        a[1] = 1
        for i in idx:
            a[i] += 1
        cum = cumsum(a)
        pt = 0
        for a, b, c, d in ABCD:
            if cum[b] - cum[a] == c:
                pt += d
        ans = max(ans, pt)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m, q = map(int, input().split())
abcds = [tuple(map(int, input().split())) for _ in range(q)]
x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ans = 0
for elem in itertools.combinations_with_replacement(x, n):
    rep = 0
    for i in range(q):
        if elem[abcds[i][1] - 1] - elem[abcds[i][0] - 1] == abcds[i][2]:
            rep += abcds[i][3]
    ans = max(ans, rep)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

nums = [(i+1) for i in range(m+1)]
ans = 0
for balls in itertools.combinations_with_replacement(nums, n):
    tp = 0
    for i in range(q):
        if balls[sc[i][1]-1]-balls[sc[i][0]-1] == sc[i][2]:
            tp += sc[i][3]
    if tp > ans:
        ans = tp

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

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

kumiawase = list(product(range(1, m + 1), repeat=n))

ans = 0
for kumi in kumiawase:
    A = [0] + list(kumi)
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if A[b] - A[a] == c:
            temp += d
    ans = max(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in [0]*q]

    que = [[0]]
    for _ in range(n):
        que2 = []
        for qq in que:
            i = qq[-1]
            for j in range(i, m+1):
                que2.append(qq+[j])
        que = que2

    ans = 0
    for q in que:
        temp = 0
        for a, b, c, d in abcd:
            if q[b]-q[a] == c:
                temp += d
        ans = max(ans, temp)
    print(ans)


main()

Submission status: Wrong Answer

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


def calc(r):
    res = 0
    for a, b, c, d in check:
        if r[b-1] - r[a-1] == c:
            res += d
    return res


def dfs(t):
    if len(t) == n:
        return calc(t)

    res = [dfs(t + [i]) for i in range(t[-1], m+1)]

    return max(res)


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

print(max(ans))

Submission status: Wrong Answer

Solution code:
ans = []
def dfs(li):
    if len(li) == n:
        ans.append(li)
        return
    else:
        for i in range(li[-1], m + 1):
            dfs(li + [i])
 
  

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

for i in range(1, m):
   dfs([i])
# print(ans)

res = 0
for ptn in ans:
    tmp = 0
    for a, b, c, d in info:
        a -= 1
        b -= 1
        if ptn[b] - ptn[a] == c:
            tmp += d
    res = max(res, tmp)
print(res)

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(1000000)

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


def dfs(a):
    if len(a) == n + 1:
        ans = 0
        for i in range(q):
            if int(a[l[i][1]]) - int(a[l[i][0]]) == l[i][2]:
                ans += l[i][3]
        anss.append(ans)
        return

    a += a[-1]
    while int(a[-1]) <= m:
        dfs(a)
        a = a[:-1] + str(int(a[-1]) + 1)
        # a = list(a)
        # a[-1] = str(int(a[-1]) + 1)
        # a = "".join(a)


def main():
    dfs(aa)
    print(max(anss))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(1000000)

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


def dfs(a):
    if len(a) == n + 1:
        ans = 0
        for i in range(q):
            if int(a[l[i][1]]) - int(a[l[i][0]]) == l[i][2]:
                ans += l[i][3]
        anss.append(ans)
        return

    a += a[-1]
    while int(a[-1]) <= m:
        dfs(a)
        a = list(a)
        a[-1] = str(int(a[-1]) + 1)
        a = "".join(a)


def main():
    dfs(aa)
    print(max(anss))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10000000)

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


def dfs(a):
    if len(a) == n + 1:
        ans = 0
        for i in range(q):
            if int(a[l[i][1]]) - int(a[l[i][0]]) == l[i][2]:
                ans += l[i][3]
        anss.append(ans)
        # print(a)
        return

    a += a[-1]
    # print("{} 1".format(a))
    while int(a[-1]) <= m:
        dfs(a)
        # print("{} 2".format(a))
        a = list(a)
        a[-1] = str(int(a[-1]) + 1)
        a = "".join(a)
        # print("{} 3".format(a))


dfs(aa)
# print(anss)
print(max(anss))

Submission status: Time Limit Exceeded

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


big_lis = []


def dfs(string, n, m):
    if n == (N - 1):
        for i in range(m, M + 1):
            big_lis.append(string + [i])
    else:
        for i in range(m, M + 1):
            dfs(string + [i], n + 1, i)


dfs([], 0, 1)

MAX_A = 0
for small_lis in big_lis:
    D = 0
    for j in range(Q):
        if small_lis[int(lis[j][1]) - 1] - small_lis[int(lis[j][0]) - 1] == int(lis[j][2]):
            D += int(lis[j][3])
    MAX_A = max(MAX_A, D)
print(MAX_A)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,Q=map(int,input().split())
q=[]
for i in range(Q):
	arr=input().split()
	q.append(arr)
A=[int(i+1) for i in range(M)]
result=list(itertools.combinations_with_replacement(A, N))
answer=0
for i in range(len(result)):
	ans=0
	for j in range(Q):
			if (result[i][int(q[j][1])-1]-result[i][int(q[j][0])-1])==int(q[j][2]):
				ans+=int(q[j][3])
	if answer<ans:
		answer=ans
	#answer.append(ans)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N,M,Q=map(int,input().split())
q=[]
for i in range(Q):
	arr=input().split()
	q.append(arr)
A=[int(i+1) for i in range(M)]
result=list(itertools.combinations_with_replacement(A, N))
answer=[]
for i in range(len(result)):
	ans=0
	for j in range(Q):
			if (result[i][int(q[j][1])-1]-result[i][int(q[j][0])-1])==int(q[j][2]):
				ans+=int(q[j][3])
	answer.append(ans)
print(max(answer))

Submission status: Time Limit Exceeded

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

a_ls=[]
b_ls=[]
c_ls=[]
d_ls=[]

for vnwrjvnwakn in range(Q):
	abcd=list(map(int, input().split()))
	a_ls+=[abcd[0]]
	b_ls+=[abcd[1]]
	c_ls+=[abcd[2]]
	d_ls+=[abcd[3]]



import itertools
As=itertools.combinations_with_replacement(range(1,M+1),N)
ans=0
for A in As:
	score=0
	for i in range(Q):
		if list(A)[b_ls[i]-1]-list(A)[a_ls[i]-1]==c_ls[i]:
			score+=d_ls[i]
	
	ans=max(ans,score)


print(ans)