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:
def increment(array, index):
  if index == -1:
    return

  array[index] += 1
  if array[index] == 10:
    array[index] = 0
    increment(array, index - 1)

n, m, q = map(int, input().split())
ans = 0
upper_limit = [m] * n
a_dict= {}
for _ in range(q):
  ai, bi, ci, di = map(int, input().split())
  a = [1] * n
  a[-1] = 0
  while a != upper_limit:
    increment(a, n-1)
     
    if 0 in a or n != len([i for i in a if i <= m]) or a != sorted(a):
      continue

    if a[bi-1] - a[ai-1] == ci:
      if tuple(a) in a_dict:
        a_dict[tuple(a)] += di
      else:
        a_dict[tuple(a)] = di

print(max(a_dict.values()))

Submission status: Time Limit Exceeded

Solution code:
def iter_p_adic(p, n):
    '''
    連続して増加するp進数をリストとして返す。nはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p+1)] * n
    return product(*tmp)


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)

MAX = 0
iterator = iter_p_adic(M,N)
for idxs in iterator:
    f = 0
    #print(idxs)
    A = list(idxs)
    A = sorted(A)
    for i in range(N):
        if A[i] == 0:
            f = 1
            break
    if f == 1:
        continue
    total = 0
    for i in range(Q):
        if c[i] == A[b[i]-1] - A[a[i]-1]:
            total += d[i]
    
    MAX = max(MAX, total)

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([0, 1], repeat=q):
    cnt = 0
    aaa = []
    aaaa = []
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
    for a, b, c in aaa[::-1]:
        for aa, bb, cc in aaa:
            if aa == a and b < bb:
                aaaa.append([b, bb, cc - c])
            elif aa == a and b > bb:
                aaaa.append([bb, b, c - cc])
            if b == bb and aa > a:
                aaaa.append([a, aa, cc - c])
            elif b == bb and aa < a:
                aaaa.append([aa, a, c - cc])
    aaa += aaaa
    flag = True
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            for aa, bb, cc in aaa:
                if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                    if aa == a and bb == b and c == cc:
                        continue
                    else:
                        flag = False
                        break
            if flag:
                cnt += d
            else:
                break
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, q = map(int, input().split())
ary = [list(map(int, input().split())) for _ in range(q)]

A = []
s1 = int("1"*N)
s9 = int("9"*N)
d10 = list(map(str, range(1, 10)))

for i in range(s1, s9+1):
    p = str(i)
    if set(p) & set(d10[M:]):
        continue
    else:
        flag = True
        for j in range(len(p)-1):
            if (p[j]) <= (p[j+1]):
                pass
            else:
                flag = False
        if flag:
            A.append(list(p))

mx = 0
for a in A:
    d = 0
    for e in ary:
        if int(a[e[1]-1]) - int(a[e[0]-1]) == e[2]:
            d += e[3]
    if mx < d:
        mx = d

print(mx)

Submission status: Time Limit Exceeded

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

abcd = [input().split() for i in range(q)]
l = list(range(1,m+1))
big_a = itertools.combinations_with_replacement(l, n)
list_a = list(big_a)
#print(list_a)
s = []
   
  
for j in range(len(list_a)):
    nowa = list_a[j]
    z = 0
    #print(abcd[z
    o =[]
    while z <= q-1:
        p = abcd[z]
        aa = int(p[0])
        bb = int(p[1])
        cc = int(p[2])
        dd = int(p[3])
        #a = int(aa)
        #b = int(bb)
        #c = int(cc)
        #d = int(dd)
       
        s_b = int(nowa[bb-1])
        s_a = int(nowa[aa-1])
        if s_b - s_a == cc:
            o.append(dd)
            #print(o)
        else:
            pass
        s.append(sum(o))
        z += 1


#print(s)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M,Q=map(int,input().split())
ABCD=[list(map(int,input().split())) for _ in range(Q)]
tl=[]
for i in range(1,M+1):
    tl.append([i])
for i in range(N):
    t=[]
    for l in tl:
        for j in range(1,M+1):
            if l[-1]<=j:
                t.append(l+[j])
    tl=t[:]
ans=0
for l in tl:
    t=0
    for a,b,c,d in ABCD:
        if l[b-1]-l[a-1]==c:
            t+=d
    ans=max(ans,t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
import itertools
comb = itertools.combinations_with_replacement(range(1, M+1), N)
MAX = 0

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

for l in comb:
  ans = 0
  for i in range(Q):
    a, b, c, d = val[i][0], val[i][1], val[i][2], val[i][3]
    if l[b-1] - l[a-1] == c:
      ans += d
  if ans > MAX:
    MAX = ans
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

q = []

for i in range(1, m+1):
    q.append(str(i-1))

while True:
    if len(q[0]) == n:
        break
    else:
        item = q.pop(0)
        for i in range(int(item[-1]), m):
            q.append(item+str(i))

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if int(item[t_item[1]-1]) - int(item[t_item[0]-1]) == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m,q = map(int, input().split())
abc = []
d = []
for _ in range(q):
    A,B,C,D = map(int, input().split())
    abc.append([A,B,C])
    d.append(D)

l = range(1,m+1)
point = 0
for v in itertools.combinations_with_replacement(l,n):
    p = 0
    for i in range(n-1):
        for j in range(i+1, n):
            if [i+1,j+1, abs(v[j]-v[i])] in abc:
                p += d[abc.index([i+1,j+1, abs(v[j]-v[i])])]
    if point < p: point = p
print(point)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

qx = []

for i in range(q):
    ma = 0
    index = 0
    for j in range(len(qz)):
        if (qz[j][2] > ma):
            ma = qz[j][2]
            index = j
    qx.append(qz[index])
    qz.pop(index)

su = [0]

def checker(af, bf):
    lt = max(af) - max(bf) + 1
    rt =[]
    for h in range(0,lt):
        amax = 0
        bf = np.array(bf)+h
        for i in range(n):
            if (af[i] != 0 and bf[i] != 0 and af[i] != bf[i]):
                break
            elif (amax > max(af[i], bf[i]) and (af[i] != 0 or bf[i] != 0)):
                break
            amax = max(amax,af[i],bf[i])
        else:
            rt.append(h)
    return rt

def adder(af, bf):
    rt = [0]*n
    for i in range(n):
        rt[i] = max(af[i], bf[i])
    return rt

ans = [[0] * n]
ans[0][qx[0][0]-1] = 1
ans[0][qx[0][1] - 1] = qx[0][2]+1
su = [qx[0][3]]

for i in range(1,q):
    a, b, c, d = map(int, qx[i])
    t = [0] * n
    t[a-1] = 1
    t[b - 1 ] = c + 1
    #print(t)
    ll = len(ans)
    for j in range(ll):
        ct = checker(ans[j], t)
        if (len(ct) != 0):
            for k in ct:
                ans.append(adder(ans[j], np.array(t)+k))
                su.append(su[j] + d)
        else:
            ans.append(t)
            su.append(d)
print(max(su))

Submission status: Time Limit Exceeded

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

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

arr = []
for i in range(2 ** Q):
    ans = [1 for i in range(N)]
    cnt = 0
    ck = 0
    
    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        cnt += d
        ans[b-1] = ans[a-1] + c

    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        if ans[b-1] - ans[a-1] != c:
          ck = 1
        if ans[b-1] > M:
          ck = 1
      
    if ck == 0:
      arr.append(cnt)

print(max(arr))

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m,q=map(int,input().split())
List=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  List.append([a,b,c,d])
List.sort()
s=-1
for i in range(2 ** q):
    l=[-1]*9
    l.insert(0,1)
    l.insert(0,1)
    point=0
    for j in range(q):
      if ((i >> j) & 1):
        point+=List[j][3]
        if l[List[j][0]]!=-1 and l[List[j][1]]!=-1 and l[List[j][1]]-l[List[j][0]]!=List[j][2]:
          l[0]=-2
          break
        else:
          if l[List[j][0]]==-1 and l[List[j][1]]!=-1:
            l[List[j][0]]=l[List[j][1]]-List[j][2]
          elif l[List[j][0]]!=-1 and l[List[j][1]]==-1:
            l[List[j][1]]=l[List[j][0]]+List[j][2]
          elif l[List[j][0]]==-1 and l[List[j][1]]==-1:
            if l[List[j][1]]!=l[List[j][1]]+List[j][2]:
              l[0]=-2
              break
    x=copy.deepcopy(l)
    while -1 in x:x.remove(-1)
    if 1<=min(x) and max(x)<=m:
          y=copy.deepcopy(x)
          x.sort()
          if x==y and point>s:
            s=point
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

#print(abcd)
A=[]
for i in range(M):
    A+=(np.zeros(N)+i).tolist()

#print(A)
d_sum_max=0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([0, 1], repeat=q):
    cnt = 0
    aaa = []
    aaaa = []
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
    for a, b, c in aaa[::-1]:
        for aa, bb, cc in aaa:
            if aa == a and b < bb:
                aaaa.append([b, bb, cc - c])
            elif aa == a and b > bb:
                aaaa.append([bb, b, c - cc])
            if b == bb and aa > a:
                aaaa.append([a, aa, cc - c])
            elif b == bb and aa < a:
                aaaa.append([aa, a, c - cc])
    aaa += aaaa
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            for aa, bb, cc in aaa:
                if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                    if aa == a and bb == b and c == cc:
                        continue
                    else:
                        break
            else:
                cnt += d
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi[::-1]) < N:
        return None
    return bi
ans = 0
for i in range((M + 1) ** (N)):
    A = n2kdigit(i, M + 1)
    # print(A)
    if A is not None:
        ans = max(ans, cal_ans([int(i) for i in A]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
aa = [0]*q
bb = [0]*q
cc = [0]*q
dd = [0]*q
for i in range(q):
    aa[i],bb[i],cc[i], dd[i] = list(map(int, input().split()))
    
import itertools
ss = set(itertools.permutations([0]*(n-1)+[1]*(m-1)))
score = 0
for tu in ss:
    tmp = 0
    xx = [1]*n
    j = 0
    for t in tu:
        if t == 0:
            j += 1
            xx[j] = xx[j-1]
        if t == 1:
            xx[j] += 1
    for i in range(q):
        if xx[bb[i]-1] - xx[aa[i]-1] ==cc[i]: 
            tmp += dd[i]
    score = max(score, tmp)
print(score)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


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

vals = np.empty((0, 4), int)
for i in range(Q):
    vals = np.append(vals, np.array([list(map(int, input().split(" ")))]), axis=0)
vals = vals[np.argsort(vals[:, 3])[::-1]]
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for i, v in enumerate(vals):
        
        if (maxv - sumv) > sum(vals[i:, 3]):
            break
        
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
#ビット全探索もどき
from itertools import combinations
vv = []
N, M, Q = map(int, input().split())
for i in range(1, M+1):
    v = i
    for j in range(N-1):
        vv.append(v)

li = []
for _ in range(Q):
    temp = list(map(int, input().split()))
    li.append(temp)

ww = []
for i in combinations(vv,N-1):
    w  = [1]
    for k in i:
        w.append(k)
    w.sort()
    ww.append(w)
#以下全探索
max_ = 0
for zz in ww:
    ss = 0
    for i in range(Q):
        a, b, c, d = li[i]
        if zz[b-1]-zz[a-1] == c:
            ss += d
    max_ = max(ss, max_)
print(max_)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from itertools import combinations_with_replacement as cwr
input = sys.stdin.readline


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)
# ind = np.argsort(np.array(D))
# A,B,C,D = np.array(A)[ind],np.array(B)[ind],np.array(C)[ind],np.array(D)[ind]
# A,B,C,D = A[::-1],B[::-1],C[::-1],D[::-1]
# Array = [0]*(N+1)
ans = 0
combs = list(cwr(np.arange(1,M+1),N))
ans = [0]*(len(combs))
for i,comb in enumerate(combs):
    for a,b,c,d in zip(A,B,C,D):
        if comb[b-1] - comb[a-1] ==c:
            ans[i] += d
print(max(ans))
# for i,d in enumerate(D):
#     a,b,c,d= A[i],B[i],C[i],D[i]
#     if Array[a] ==0:
#         Array[a] = a
#     if Array[b] == 0:
#         Array[b] = a+c
#     if Array[b] - Array[a] == c:
#         ans += d

Submission status: Time Limit Exceeded

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

num_all = [i+1 for i in range(M)]
#print(num_all)
Comb = list(itertools.combinations_with_replacement(num_all,N))

num_l = []         
for i in range(Q):
  a,b,c,d = map(int,input().split())
  num_l.append([a,b,c,d])
#print(num_l)  
  
#print(len(Comb))
d_sum_max = 0  
for A in Comb:
  d_sum = 0
  #print(A)
  #print()
  
  for i in range(Q):
    a,b,c,d = num_l[i][0],num_l[i][1],num_l[i][2],num_l[i][3]
    #print(a,b,c,d)
    #print(A[b-1],A[a-1],':',A[b-1]-A[a-1],c)
    if(A[b-1]-A[a-1] == c):
      d_sum += d
      
  #print(A,d_sum)
  d_sum_max = max(d_sum_max,d_sum)

print(d_sum_max)

Submission status: Time Limit Exceeded

Solution code:
import itertools

#a, b, c, d = map(int, input().split())

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

s = [input().split() for i in range(Q)]

#print(s)

A = list(itertools.combinations_with_replacement(range(1,M+1), N))


kotae=0

high_kotae=0

for i in range(len(A)):
    kotae=0
    for j in range(Q):
        if A[i][int(s[j][1])-1]-A[i][int(s[j][0])-1]==int(s[j][2]):
            kotae+=int(s[j][3])
    if high_kotae<kotae:
        high_kotae=kotae
print(high_kotae)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n, m, q = map(int, input().split())
vec = [0]
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(m):
    for j in range(len(it) - 1): vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]: na.append(j)
        if b[i] == it[j]: nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]: cnt += d[i]
    if ans < cnt: ans = cnt
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
a = []
for i in range(q):
    a.append(input().split())

ans = 0
l = [i for i in range(m)]
for v in itertools.combinations_with_replacement(l, n):
    ans_ = 0
    for j in range(q):
        if v[int(a[j][1])-1] - v[int(a[j][0])-1] == int(a[j][2]):
            ans_ += int(a[j][3])
    if ans_ > ans:
        ans = ans_

print(ans)

Submission status: Time Limit Exceeded

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

a = []
def gen_a(n,ai,cur):
    if n==0:
        for k in range(1,M+1):
            if k==10:
                k = "a"
                gen_a(1,10,str(k))
            else:
                gen_a(1,k,str(k))
    elif n==N:
        ar = list(cur)
        if ar[-1] == "a": ar[-1] = "10"
        a.append(ar)
    else:
        for k in range(ai,M+1):
            if k == 10:
                k = "a"
                gen_a(n+1,10,cur+str(k))
            else: 
                gen_a(n+1,k,cur+str(k))

gen_a(0,1,0)

ans = 0
for a_item in a:
    cnt = 0
    for d_item in data:
        nb = int(a_item[d_item[1]-1]) if a_item[d_item[1]-1] != "a" else 10
        na = int(a_item[d_item[0]-1]) if a_item[d_item[0]-1] != "a" else 10
        if nb - na == d_item[2]:
            cnt += d_item[3]
    if ans < cnt:
        ans = cnt

print(ans)

Submission status: Time Limit Exceeded

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

A = [chr(i) for i in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
nmq = input().split()
nn = nmq[0]
mm = nmq[1]
qq = nmq[2]
n = int(nn)
m = int(mm)
q = int(qq)
abcd = [input().split() for i in range(q)]
l = list(range(1,m+1))
big_a = itertools.combinations_with_replacement(l, n)
list_a = list(big_a)
#print(list_a)
s = []
   
  
for j in range(len(list_a)):
    nowa = list_a[j]
    z = 0
    #print(abcd[z
    o =[]
    while z <= q-1:
        p = abcd[z]
        aa = p[0]
        bb = p[1]
        cc = p[2]
        dd = p[3]
        a = int(aa)
        b = int(bb)
        c = int(cc)
        d = int(dd)
       
        s_b = int(nowa[b-1])
        s_a = int(nowa[a-1])
        if s_b - s_a == c:
            o.append(d)
            #print(o)
        else:
            pass
        s.append(sum(o))
        z += 1


#print(s)
print(max(s))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

arr = []
for i in range(2 ** Q):
    ans = [1 for i in range(N)]
    cnt = 0
    ck = 0
    
    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        cnt += d
        ans[b-1] = ans[a-1] + c

    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        if ans[b-1] - ans[a-1] != c:
          ck = 1
        
    for k in range(N-1):
      if ans[k] > ans[k+1]:
        ck = 1
      elif ans[k] > M:
        ck = 1
    if ans[-1] > M:
      ck = 1
      
      
    if ck == 0:
      arr.append(cnt)

print(max(arr))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 0
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi[::-1]) < N:
        return None
    return bi
ans = 0
for i in range(M ** (N)):
    A = n2kdigit(i, M)
    if A is not None:
        ans = max(ans, cal_ans([int(i) for i in A]))
ans = max(ans, cal_ans([0 for i in range(N)]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
li = []
for q in range(Q):
    a, b, c, d = map(int, input().split())
    li.append([[a,b], c, d])
ok_list = []
def dfs(num_li, depth):
    if len(num_li) == N:
        ok_list.append(num_li)
        return
    if depth == M:
        return
    dfs(num_li, depth+1)
    while len(num_li) <N:
        num_li += str(depth)
        dfs(num_li, depth+1)
dfs("", 0)
maxpoint = 0
for ok in ok_list:
    point = 0
    for q in range(Q):
        if int(ok[li[q][0][1]-1])- int(ok[li[q][0][0]-1]) == li[q][1]:
            point += li[q][2]
    if point > maxpoint:
        maxpoint = point
print(maxpoint)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
conditions = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    conditions.append([a, b, c, d])
lists = []
for i in range(10**(n-1), 10**n):
    l = [int(x) for x in list(str(i))]
    for j in range(n):
        if l[j] == 0:
            l[j] = 10
    lists.append(l)
lists2 = []
for l in lists:
    for j in range(n):
        if l[j] > m:
            break
    else:
        lists2.append(l)
lists3 = []
for l in lists2:
    for j in range(1, n):
        if l[j - 1] > l[j]:
            break
    else:
        lists3.append(l)
best_point = 0
for l in lists3:
    point = 0
    for i in range(q):
        if l[conditions[i][1] - 1] - l[conditions[i][0] - 1] == conditions[i][2]:
            point += conditions[i][3]
        # print(l, conditions[i], point)
    if point > best_point:
        best_point = point
print(best_point)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

for i in range(1,M+1,1):
    for j in range(N):
        L.append(i)

A = []
B = []
C = []
D = []
for _ in range(Q):
    a,b,c,d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

List = list(itertools.combinations(L, N))
ans = 0
for l in List:
    temp = 0
    for q in range(Q):
        if (l[B[q]-1]-l[A[q]-1])==C[q]:
            temp = temp + D[q]
    ans = max(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

from operator import itemgetter
from copy import deepcopy

rlist = []
def dfs(i1,r1,alist1,q,qlist):
    if i1 >= q:
        rlist.append(r1)
    else:
        eq = qlist[i1]
        eq0 = eq[0]
        eq1 = eq[1]
        eq2 = eq[2]
        eq3 = eq[3]
        if alist1[eq0] != -1 and alist1[eq1] != -1 and alist1[eq1] - alist1[eq0] == eq2:
            r1 += eq3
        alist1t1 = deepcopy(alist1)
        dfs(i1+1, r1, alist1t1,q,qlist) #alistを変えずに再帰
        alist1t2 = deepcopy(alist1)
        if alist1t2[eq1] == -1 and alist1t2[eq0] == -1:
            alist1t2[eq1] = 100000
            alist1t2[eq0] = 100000 - eq2
            r1 += eq3
        elif alist1t2[eq1] == -1 and alist1t2[eq0] != -1:
            alist1t2[eq1] = alist1t2[eq0] + eq2
            r1 += eq3
        elif alist1t2[eq1] != -1 and alist1t2[eq0] == -1:
            alist1t2[eq0] = alist1t2[eq1] - eq2
            r1 += eq3
        dfs(i1+1,r1,alist1t2,q,qlist)

def main():
    n, m, q = map(int, input().split())
    qlist = []
    for _ in range(q):
        qlist.append(tuple(map(int, input().split())))
    qlist.sort(key=itemgetter(3), reverse=True)
    alist = [-1] * (n + 1)
    r = 0
    dfs(0,r,alist,q,qlist)
    print(max(rlist))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

n, m, q = list(map(int, input().split(" ")))
abcd = [list(map(int, input().split(" "))) for _ in range(q)]
max_point = 0
for a_list in product(list(range(1, m + 1)), repeat=n):
    a_list = sorted(a_list)
    point = 0
    for a, b, c, d in abcd:
        if a_list[b - 1] - a_list[a - 1] == c:
            point += d
    max_point = max(max_point, point)
print(max_point)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


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

vals = np.empty((0, 4), int)
for i in range(Q):
    vals = np.append(vals, np.array([list(map(int, input().split(" ")))]), axis=0)
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor

from collections import defaultdict, deque,Counter
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n, m, q = map(int, input().split())
    l = [tuple(map(int, input().split())) for _ in range(q)]
    ans = 0
    for i in range(2 ** q):  # とるかとらないかの2択
        check = [0] * q
        for j in range(q):
            if i >> j & 1:
                check[j] = 1
        # print(check)
        A = [1] * n
        used = [0] * n
        tmp = 0
        for k in range(q):
            if check[k]:  # とる時
                a, b, c, d = l[k]
                a -= 1
                b -= 1
                if not used[b]:  # 使ってない時は変更できる
                    A[b] = c + A[a]
                    tmp += d
                    used[b] = 1  # 変更ずみにする
                    used[a] = 1
                    if A[b] > m:  # m以上の場合はダメ
                        tmp = 0
                        break
                elif A[b] == c + A[a]:  # たまたま変更してからあってたら追加
                    tmp += d
                else:  # 条件に合わない場合
                    tmp = 0
                    break
        ans = max(ans, tmp)
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(x) for x in input().split()]

list_a = []
list_b = []
list_c = []
list_d = []

for i in range(Q):
    a, b, c, d = [int(x) for x in input().split()]
    list_a.append(a)
    list_b.append(b)
    list_c.append(c)
    list_d.append(d)

def get_score(A):
    score = 0
    # print(A)
    for i in range(Q):
        if A[list_b[i]-1] - A[list_a[i]-1] == list_c[i]:
            score += list_d[i]
    return score

import numpy as np
A = np.array([1] * N)


def iterate_A(A):
    k = (A == M).sum()
    # print(k, N)
    if k == N:
        return None
    if k == 0:
        A[-1] += 1
        return A
    nxt = A[-1-k] + 1
    A[-1-k] = nxt
    # print('n', nxt)
    for i in range(k):
        A[-1-i] = nxt
    return A


max_score = 0
lim_score = sum(list_d)
while A is not None:
    # print(A)
    # score = get_score(A)
    # if score > max_score:
    #     # print(A, score)
    #     max_score = score
    max_score = max(max_score, get_score(A))
    if lim_score == max_score:
        break

    A = iterate_A(A)

print(max_score)