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: Time Limit Exceeded

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

data = [0]*q;
for i in range(q):
    data[i] = list(map(int,input().split()));

A = [1]*n;
ans = 0;
As = [A];

for i in As :
    A_now = As.pop(0);
    for j in range(n) :
        if A_now[j] < m :
            A_next = [A_now[j]+1]*n;
            for k in range(j) :
                A_next[k] = A_now[k];
            As.append(A_next);
    ans_now = 0;
    for j in range(q) :
        if A_now[data[j][1]-1] - A_now[data[j][0]-1] == data[j][2] :
            ans_now += data[j][3];
    if ans_now>ans :
        ans = ans_now;


print(ans);

Submission status: Time Limit Exceeded

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

A_N = [[i] for i in range(1, M+1)]
for i in range(N-1):
  a = []
  for j in range(len(A_N)):
    last = A_N[j][-1]
    for k in range(last, M+1):
      a.append(A_N[j] + [k])
  A_N = a

high_score = 0
for i in range(len(A_N)):
    A = A_N[i]
    score = 0
    for j in range(len(l)):
        aj, bj, cj, dj = l[j]
        if A[bj-1]-A[aj-1] == cj:
            score += dj
        high_score = max(high_score, score) 
        
print(high_score)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
from math import factorial
n,m,q=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(q)]
total=[]
for a in combinations_with_replacement(range(1,m+1),n):
  ans=0
  for j in range(q):
    if int(a[lst[j][1]-1])-int(a[lst[j][0]-1])==lst[j][2]:
      ans+=lst[j][3]
  total.append(ans)

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
S=[[0 for i in range(4)] for j in range(Q)]
for i in range(Q):
    inputS=list(map(int,input().split()))
    S[i][0]=inputS[0]
    S[i][1]=inputS[1]
    S[i][2]=inputS[2]
    S[i][3]=inputS[3]
S2=[]
maxNum=0
for a in range(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):
                                        S2.append([a,b,c,d,e,f,g,h,i,j])
                                        
                                        count=0
                                        for k in range(Q):
                                            if S2[len(S2)-1][S[k][1]-1]-S2[len(S2)-1][S[k][0]-1]==S[k][2]:
                                                count+=S[k][3]
                                        maxNum=max(maxNum,count)

print(maxNum)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))

Submission status: Time Limit Exceeded

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

max_score = 0
for mid in itertools.product(range(m),repeat=n-1):
    if sum(mid)>m-1:
        continue
    tmp_score=0
    for i in qs:
        sum_mid = 0
        for j in range(i[0]-1,i[1]-1):
            sum_mid += mid[j]
        if sum_mid == i[2]:
            tmp_score += i[3]
    if tmp_score > max_score:
        max_score = tmp_score
        
print(max_score)

Submission status: Time Limit Exceeded

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

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

import itertools

pre=[]
for i in range(m):
    pre+=[0]

for i in range(n):
    pre+=[1]

#print(pre)

junretsu = list(set(itertools.permutations( pre )))
junretsu.sort()
#print(len(junretsu))

ans=0

for i in junretsu:
    cnt0 = 0
    t = []
    for j in range(n+m):
        if i[j] == 0:
            cnt0 += 1
        else:
            t.append(cnt0)
    #print(t)
    if 0 in t:
        continue
    score=0
    for a,b,c,d in data:
        if t[b] - t[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M, Q = mi()
abcd = li2(Q)

'''
a = '0' * N
m = str(M-1)
l = [a]

while True:
    i = N-1
    while i >= 0 and a[i] == m:
        i -= 1
    if i == -1:
        break
    a = list(a)
    num = str(int(a[i]) + 1)
    a[i] = num
    if i != N-1:
        for j in range(i+1, N):
            a[j] = num
    tmp = ''.join(a)
    l.append(tmp)
'''

def dfs(num, length):
    if length == N:
        l.append(num)
        return
    last = int(num[-1])
    for i in range(last, M):
        dfs(num + str(i), length+1)

#l = []
#dfs('0', 1)

from collections import deque
keta_list = [str(i) for i in range(M)]
l = deque([str(i) for i in range(M)])

while len(l[0]) <= N:
    num = l.popleft()
    last = int(num[-1])
    for tail in keta_list[last:]:
        l.append(num + tail)

ans = 0
for num in l:
    cnt = 0
    num = list(map(int, list(num)))
    for i in range(Q):
        if num[abcd[i][1]-1] - num[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
#めっちゃfor分あるならdfs
def dfs(d,s):
    global n,m,Q,ans
    if d==n-1:
        ans_=0
        for k in Q:
            a,b,c,d=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=d
        ans=max(ans,ans_)
    else:
        l=int(s[-1])
        [dfs(d+1,s+str(i)) for i in range(l,m+1)]
for i in range(1,m+1):
    dfs(0,str(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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())


sequences = []
def dfs(s):
    if len(s) == N:
        sequences.append(s)
        return
    if s == '':
        tail_num = 1
    else:
        tail_num = int(s[-1])
    for nxt_d in range(tail_num,M+1):
        dfs(s+str(nxt_d))
dfs('')

ans = 0
for seq in sequences:
    score = 0
    for i in range(Q):
        if int(seq[b[i] - 1]) - int(seq[a[i] - 1]) == c[i]:
            score += d[i]
    ans = max(ans, score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
#めっちゃfor分あるならdfs
def dfs(d,s):
    global n,m,Q,ans
    if d==n-1:
        ans_=0
        for k in Q:
            a,b,c,d=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=d
        ans=max(ans,ans_)
    else:
        l=int(s[-1])
        for i in range(l,m+1):
            dfs(d+1,s+str(i))
for i in range(1,m+1):
    dfs(0,str(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
 
s=[list(map(int,list(input().split()))) for i in range(q)] 
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[s[i][1]-1]) - int(retsu[s[i][0]-1]) == s[i][2]:
            tmp = tmp + s[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    # 入力パターン．
    # 先に要素数Nが与えられて，その数読み込むパターン
    ### N
    ### x_1, y_1
    ### ...
    ### x_N, y_N
    N, M, Q = map(int, input().split())
    data = np.array([list(map(int, input().split())) for _ in range(Q)])
    #print(data)
    # A = data[:, 0]
    # B = data[:, 1]
    # C = data[:, 2]
    # D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = combinations_with_replacement(range(1, M+1), N)
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        for i in range(Q):
            if a[data[i, 1]-1] - a[data[i, 0]-1] == data[i, 2]:
                s += data[i, 3]
        if s > ans:
            ans = s
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(p):
    ret = 0
    # 各条件を満たしていれば、dを加算していく
    for a, b, c, d in abcd:
        if p[b-1] - p[a-1] == c:
            ret += d
    return ret

ans = [0]
def dfs(s, n):
    if n == N:
        ans[0] = max(ans[0], calc(list(map(int,s))))
        return
    for i in range(int(s[-1]),M+1):
        dfs(s+str(i), n+1)

for i in range(1, M+1):
    dfs(str(i), 1)

print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    # 入力パターン．
    # 先に要素数Nが与えられて，その数読み込むパターン
    ### N
    ### x_1, y_1
    ### ...
    ### x_N, y_N
    N, M, Q = map(int, input().split())
    data = np.array([list(map(int, input().split())) for _ in range(Q)])
    #print(data)
    # A = data[:, 0]
    # B = data[:, 1]
    # C = data[:, 2]
    # D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = list(combinations_with_replacement(range(1, M+1), N))
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        for i in range(Q):
            if a[data[i, 1]-1] - a[data[i, 0]-1] == data[i, 2]:
                s += data[i, 3]
        if s > ans:
            ans = s
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, q = [int(x) for x in input().split()]
abcd = [[int(x) for x in input().split()] for _ in range(q)]
all_pattern = []
start = '1'
def dfs(s):
    last_s = int(s[-1])
    next_s = [str(x) for x in range(last_s, m + 1)]
    for i in next_s:
        t = s + i
        if len(t) == n + 1:
            all_pattern.append(t[1:])
        else:
            dfs(t)
dfs(start)
ans = 0
for pattern in all_pattern:
    res = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if int(pattern[b - 1]) - int(pattern[a - 1]) == c:
            res += d
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

A = []
for m in range(1, M + 1):
    for n in range(N):
        A.append(m)
#print(A)

ans_max = 0
for AA in itertools.combinations(A, N):
    ans = 0
    for ll in L:
        a = ll[0]
        b = ll[1]
        c = ll[2]
        d = ll[3]
        Ab = AA[b-1]
        Aa = AA[a-1]
        s = Ab - Aa
        if (s == c):
            ans += d
    if (ans_max < ans):
        ans_max = ans
print(ans_max)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
co=[]
def dfs(d,s):
    global n,co,m
    if d==n-1:
        co.append(s)
    else:
        l=int(s[-1])
        for i in range(l,m+1):
            dfs(d+1,s+str(i))
for i in range(1,m+1):
    dfs(0,str(i))
ans=0
for i in co:
    ans_=0
    for k in range(q):
        a,b,c,d=Q[k]
        if int(i[b-1])-int(i[a-1])==c:
            ans_+=d
    ans=max(ans,ans_)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = 0
for bit in product([0, 1], repeat=q):
    tmp = [1] * (n + 1)
    bl = [0] * (n + 1)
    f = True
    for i, j in enumerate(bit):
        if j == 1:
            if bl[abcd[i][1]] == 1:
                if bl[abcd[i][0]] == 1:
                    if tmp[abcd[i][0]] != tmp[abcd[i][1]] - abcd[i][2]:
                        f = False
                        break
                else:
                    tmp[abcd[i][0]] = tmp[abcd[i][1]] - abcd[i][2]
                    bl[abcd[i][0]] = 1
            else:
                tmp[abcd[i][1]] = tmp[abcd[i][0]] + abcd[i][2]
                bl[abcd[i][1]] = 1
    pre = tmp[0]
    for i in range(1, n):
        if bl[i] == False:
            tmp[i] = tmp[i-1]
        if pre > tmp[i]:
            f = False
            break
        pre = tmp[i]
    if f:
        cnt = 0
        for i, j in enumerate(bit):
            if j == 1:
                cnt += abcd[i][3]
        ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    # 入力パターン．
    # 先に要素数Nが与えられて，その数読み込むパターン
    ### N
    ### x_1, y_1
    ### ...
    ### x_N, y_N
    N, M, Q = map(int, input().split())
    data = np.array([list(map(int, input().split())) for _ in range(Q)])
    #print(data)
    A = data[:, 0]
    B = data[:, 1]
    C = data[:, 2]
    D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = list(combinations_with_replacement(range(1, M+1), N))
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        for i in range(Q):
            t = a[B[i]-1]
            t = a[A[i]-1]
            t =C[i]
            if a[B[i]-1] - a[A[i]-1] == C[i]:
                s += D[i]
        if s > ans:
            ans = s
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)] 
u=[]
for i in range(1,m+1):
  for k in range(n):
    u.append(i)
a=list(set(list(itertools.combinations(u,n))))
ans=[]

for i in range(len(a)):
  c=0
  for k in range(len(l)):
    if a[i][l[k][1]-1]-a[i][l[k][0]-1]==l[k][2]:
      c+=l[k][3]
  ans.append(c)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

from numpy import array_split
arrays = list(array_split(aa, q))

solve(n, m, q, arrays)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
c = []
 
for i in range(q):
    c.append([int(j) for j in input().split()])
 
nums = range(1, m + 1)
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[c[i][1]-1]) - int(retsu[c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
    c.append([int(j) for j in input().split()])
 
nums = range(1, m + 1)
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[c[i][1]-1]) - int(retsu[c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

n, m, q = map(int, input().split())
a = np.zeros(q, dtype=int)
b = np.zeros(q, dtype=int)
c = np.zeros(q, dtype=int)
d = np.zeros(q, dtype=int)

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

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]
        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

import numpy as np
arrays = list(np.array_split(aa, q))

solve(n, m, q, arrays)

Submission status: Time Limit Exceeded

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

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


for i in range(1, 10):
    dfs([i])

ans = 0
for i in range(len(A)):
    now = A[i]
    point = 0
    for j in range(q):
        a, b, c, d = abcd[j]
        a -= 1
        b -= 1
        if int(now[b]) - int(now[a]) == c:
            point += d

    ans = max(ans, point)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    a,b,c,d=(l[i][j] for j in range(4))
    if x[b]-x[a]==c:
      p+=d
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in itertools.combinations_with_replacement(r,n):
  p=checker(i,l)
  if p>point:
    point=p
print(point)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

M=0
for l in map(list,itertools.combinations(range(1,n+m),n)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if l[bj-1]-bj-l[aj-1]+aj==cj:
            s+=dj
    M=max(M,s)
print(M)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,Q = map(int,input().split())

numbers = deque([[i+1] for i in range(M)])

for i in range(N):
    a = deque([])
    while numbers:
        l = numbers.pop()
        b = l[-1]
        for j in range(b,M+1):
            a.append(l+[j])
    numbers = a

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

ans = 0
while numbers:
    cnt = 0
    L = numbers.pop()
    for x in X:
        a,b,c,d = x
        if L[b-1]-L[a-1]==c:
            cnt+=d
    ans = max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

M=0
for l in map(list,itertools.combinations(range(1,n+m),n)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if (l[bj-1]-(bj-1))-(l[aj-1]-(aj-1))==cj:
            s+=dj
    M=max(M,s)
print(M)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
g=itertools.combinations_with_replacement(r,n)
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    a,b,c,d=(l[i][j] for j in range(4))
    if x[b]-x[a]==c:
      p+=d
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in g:
  p=checker(i,l)
  if p>point:
    point=p
print(point)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

A = [0, 1]
combnation = list(product(A, repeat=Q))
abcd.sort()

ans = 0
for comb in combnation:
    comb_list = [abcd[i] for i, k in enumerate(comb) if k==1]
    check = True
    A = [0 for i in range(N+1)]
    amount = 0
    for a, b, c, d in comb_list:
        amount += d
        if A[a] == 0 and A[b] == 0:
            if A[a] == 0 and A[b] == 0:
                A[a] = 1
                A[b] = 1 + c
    
        elif A[a] == 0 and A[b] != 0:
            if A[b] - c >= 1:
                A[a] = A[b] - c
            else:
                check = False
    
        elif A[a] != 0 and A[b] == 0:
            if c + A[a] <= M:
                A[b] = A[a] + c
            else:
                check = False
        else:
            if A[b] - A[a] != c:
                check = False
        
    
    if check and amount > ans:
        ans = amount
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
g=itertools.combinations_with_replacement(r,n)
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    a,b,c,d=(l[i][j] for j in range(4))
    if x[b]-x[a]==c:
      p+=d
  return p
def mini(x):
  m=0
  for i in range(len(x)):
    if x[i]!=None:
      if x[i]<m:
        m=x[i]
  return m
def maxe(x):
  m=0
  for i in range(len(x)):
    if x[i]!=None:
      if x[i]>m:
        m=x[i]
  return m
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
l.sort(key=lambda x:x[3])
for i in g:
  p=checker(i,l)
  if p>point:
    point=p
print(point)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

Alist=list(map(list,itertools.combinations(range(1,n+m),n)))

slist=[]
for i in range(len(Alist)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if (Alist[i][bj-1]-(bj-1))-(Alist[i][aj-1]-(aj-1))==cj:
            s+=dj
    slist.append(s)

print(max(slist))

Submission status: Time Limit Exceeded

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

stack = [i for i in range(1, M + 1)]

for i in range(N - 1):
    tmp = []
    while stack:
        now = stack.pop()
        start = now % 10
        for i in range(start, M + 1):
            tmp.append(now * 10 + i)
    stack = tmp

ans = 0
for tmp in stack:
    point = 0
    tmp1 = str(tmp)
    for a, b, c, d in ABCD:
        if int(tmp1[b - 1]) - int(tmp1[a - 1]) == c:
            point += d
    ans = max(ans, point)

print (ans)
# print (stack)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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())

A = np.array(list(itertools.combinations_with_replacement(range(1, m + 1), n)))

cnt = 0

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

Submission status: Time Limit Exceeded

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    
import itertools
it = itertools.combinations_with_replacement(tmp_A, n)
for base in list(it):
    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-1 <= len(base) and f-1 <= len(base):
            if (base[f-1] - base[e-1]) == g:
                res += h
            if res >= top:
                top = res         
print(top)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.product(range(1, m+1), repeat=n))

    maxp = 0
    for x in pattern:
        if sorted(x) != list(x):
            continue
        
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

import numpy as np
arrays = list(np.array_split(aa, q))

solve(n, m, q, arrays)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

Alist=[]

for l in itertools.combinations(range(1,n+m),n):
    ll=list(l)
    a=[]
    for i in range(n):
        a.append(ll[i]-i)
    Alist.append(a)

slist=[]
for i in range(len(Alist)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if Alist[i][bj-1]-Alist[i][aj-1]==cj:
            s+=dj
    slist.append(s)

print(max(slist))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, Q = MAP()
L = [LIST() for i in range(Q)]

B = [i for i in range(1, M+1)]


num = N #生成するビット数
bit_list = list(product(B, repeat=N))

# print(bit_list)
# exit()
A_list = []

for b in bit_list:
    b = list(b)
    b.sort()
    # A_list.append(b)
    if b not in A_list:
        A_list.append(b)
# print(len(A_list))

ans = 0
# print(A_list)
for A in A_list:
    tmp = 0
    # print(A)
    for a, b, c, d in L:
        if A[b-1] - A[a-1] == c:
            tmp += d
    # print(tmp)
    ans = max(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

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

ls = [0] * n + [1] * (m - 1)
mx = 0
for l in itertools.permutations(ls):
    a = [0]
    idx = 1
    for i in l: 
        if i == 0: a.append(idx)
        else: idx += 1
    #print(l, a)
    v = 0
    for i in query:
        if a[i[1]] - a[i[0]] == i[2]: v += i[3]
    mx = max(v, mx)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
# N = list(map(int, input()))[::-1]
# N = int(input())
N, M, Q = map(int, input().split())
big = 0
s = 2**N
l = []

moto = list(range(1, Q+1))

for i in range(Q):
    l.append(list(map(int, input().split())))

A = []
for i in range(N):
    AA = []
    if A:
        for k in A:
            for j in range(1, M+1):
                if int(k[-1]) <= j:
                    AA.append(k+str(j))
        A = AA
    else:
        for j in range(1, M+1):
            A.append(str(j))

for i in A:
    wa = 0
    for j in l:
        if (int(i[j[1]-1])-int(i[j[0]-1])) == j[2]:
            wa += j[3]

    if big < wa:
        big = wa
print(big)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
 
n,m,q = map(int,input().split())
li=[input() for i in range(q)]
 
ans_list=list()
ans=0
xans=0
 
lis =  list(range(1,m+1))
for team in itertools.combinations_with_replacement(lis,n):
  
    for i in range(q):
      
      lix=li[i].split()
      
      if team[int(lix[1])-1]-team[int(lix[0])-1]==int(lix[2]):
        ans=int(lix[3])
        xans+=ans
        
       
        
    ans_list+=[xans]
    xans=0
      
    
    
print(max(ans_list))