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

ans=0
for i in range(2**q):
  t_ans=0
  x=[1 for i in range(n)]
  for j in range(q):
    if (i>>j)&1:
      a,b,c,d=l[j]
      a-=1
      b-=1
      t_ans+=d
      if x[b]-x[a]==c:
        pass
      else:
        x[b]=x[a]+c

  check=1
  before=x[0]
  for i in x[1:]:
    if i>=before:
      before=i
    else:
     check=0

  t_ans=0
  for a,b,c,d in l:
    a-=1
    b-=1
    if x[b]-x[a]==c:
      t_ans+=d
  ans=max(ans,t_ans)

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

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
# 10進数のnを2進数のリストに変換
# def n2kdigit(n,k):
#     digits = []
#     before = 0
#     while n > 0:
#         if before > n % k:
#             return None
#         digits.append(n % k)
#         before = n % k
#         n = n // k
#     if len(digits) < N:
#         return None

#     return digits
def n2kdigit(n, k):
    bi=''
    before = 0
    while n!=0:
        if before <= (n % k):
            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 = -1
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:
import copy

t_list = []
n, m, q = map(int, input().split())
my_set = set()
for i in range(q):
    t_list.append(list(map(int, input().split())))
    my_set.add(t_list[-1][0]-1)
    my_set.add(t_list[-1][1]-1)

q = []

for i in range(1, m+1):
    q.append([i])

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

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - 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())
a=[]
ind_add = []
for _ in range(Q):
  tmp = list(map(int, input().split()))
  a.append(tmp)
  ind_add.append(tmp[0])
  ind_add.append(tmp[1])

ind_add = list(set(ind_add))
ind_add = [n-1 for n in ind_add]
len_ind = len(ind_add)

l = list(range(1, M+1))

p = itertools.product(l, repeat=len_ind)

def check_ord(t):
  for i in range(len_ind-1):
    if t[ind_add[i]] > t[ind_add[i+1]]:
      return False
  return True

def reshape_list(t):
  tt = [-1]*N
  for i in range(len_ind):
    tt[ind_add[i]] = t[i]
  return tt

n = 0
for t_p in p:
  t_p = reshape_list(t_p)
  tmp_n = 0
  if not check_ord(t_p):
    continue
  # print(t_p)

  for i in range(Q):
    if t_p[a[i][1]-1] - t_p[a[i][0]-1] == a[i][2]:
      tmp_n += a[i][3]
  
  if tmp_n > n:
    n = tmp_n

print(n)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

lis = []
for i in range(1, M+1):
    for j in range(N):
        lis.append(i)
box = set(combinations(lis, N))

ans = []
for i in box:
    temp = 0
    for a, b, c, d in abcd:
        if i[b-1] - i[a-1] == c:
            temp += d
    ans.append(temp)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]
maxd=0
for i in range(2**q):
  cnt=0
  a=[1]*n
  flag=0
  for j in range(q):
    if (i>>j)&1:
      t=a[(l[j][1])-1]
      a[(l[j][1])-1]+=(a[(l[j][0])-1]+l[j][2]-t)
  for j in range(q):
    if (a[(l[j][1])-1]-a[(l[j][0])-1])==l[j][2]:
      cnt+=l[j][3]
  if a[n-1]<=m:
    if cnt>maxd:
      maxd=cnt
print(maxd)

Submission status: Time Limit Exceeded

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

def g():
    global N,M,Q,L,check,ans
    ret =[]
    S = 0
    for i in range(Q):
        if(check[i] == 1):
            S += L[i][3]
            ret.append(L[i])
    ret.sort(key = lambda t:(t[0],t[1]))
    if(len(ret) ==0):
        return 0
    
    chk = [0]* 100
    chk[ret[0][0]] = 1

    D = [True] * 100
    Que = [ret[0][0], ret[0][1]]

    while(len(Que) > 0):
        F = Que.pop(0)
        D[F] = False
        if(chk[F] == 0):
            chk[F] = 1

        for i in range(len(ret)):
            if(ret[i][0] == F):
                chk[ret[i][1]] = chk[F] + ret[i][2]
                if D[ret[i][1]]:
                    Que.append(ret[i][1])
        
    for i in range(len(ret)):
        if chk[ret[i][1]] - chk[ret[i][0]] != ret[i][2]:
            return 0
        if chk[i] > M:
            return 0
    else:
        if ans < S:
            ans = S


def dfs(k):
    global check
    if k == Q-1:
        for i in range(2):
            check[k] = i
            g()
    else:
        for i in range(2):
            check[k] = i
            dfs(k+1)


dfs(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from itertools import combinations

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

D = defaultdict(set)
for a, b, c, d in ABCD:
  D[b-1].add((a-1, c, d))

for j in range(N-1, 0, -1):
  for x, y in combinations(D[j], 2):
    if x[0] == y[0]:
      continue
    if x[0] > y[0]:
      x, y = y, x
    if x[1] > y[1]:
      D[y[0]].add((x[0], x[1] - y[1], 0))

for j in range(1, N):
  D[j].add((j-1, 0, 0))

que = deque([([1], 0)])
ans = 0
ans_L = []
while que:
  L, score = que.popleft()
  if len(L) == N:
    if score > ans:
      ans = score
      ans_L = L
  else:
    for a, c, d in D[len(L)]:
      l = L[a] + c
      if l <= M:
        que.append((L + [l], score + sum(d for a, c, d in D[len(L)] if l - L[a] == c)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

lis = []
for i in range(1, M+1):
    for j in range(N):
        lis.append(i)
box = list(combinations(lis, N))

ans = []
for i in box:
    temp = 0
    for a, b, c, d in abcd:
        if i[b-1] - i[a-1] == c:
            temp += d
    ans.append(temp)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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, b, c, d]

lis = []
for i in range(m):
    for j in range(n):
        lis.append(i+1)
pat = list(itertools.combinations(lis, n))

ans = 0
for l in pat:
    cnt = 0
    for i in range(q):
        if l[abcd[i][1]-1] - l[abcd[i][0]-1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

tmp = 0
max = 0
tmpmax=0
c = []

for i in range(q):
    c.append([int(j) for j in input().split()])

for i in range(q):
    tmpmax = tmpmax + c[i][3]

for i in range(1,m+1):
    l.append(str(i))
a = list(itertools.combinations_with_replacement(l, n))

for k in range(len(a)): 
    for i in range(q):
        if int(a[k][c[i][1]-1]) - int(a[k][c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
        if tmpmax == max:
            print(max)
            exit()
    tmp = 0

print(max)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor
import numpy as np
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
                elif A[b] == c + A[a]:  # たまたま変更してからあってたら追加
                    tmp += d
                else:  # 条件に合わない場合
                    tmp = 0
                    break
        if max(A) > m:  # Aの最大値がm以下である
            tmp = 0
        ans = max(ans, tmp)
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def g():
    global N,M,Q,L,check,ans
    ret =[]
    S = 0
    for i in range(Q):
        if(check[i] == 1):
            S += L[i][3]
            ret.append(L[i])
    ret.sort(key = lambda t:(t[0],t[1]))
    if(len(ret) ==0):
        return 0
    
    chk = [0]* 1000
    chk[ret[0][0]] = 1

    D = [True] * 1000
    Que = [ret[0][0], ret[0][1]]

    while(len(Que) > 0):
        F = Que.pop(0)
        D[F] = False
        for i in range(len(ret)):
            if(ret[i][0] == F):
                chk[ret[i][1]] = chk[F] + ret[i][2]
                if D[ret[i][1]]:
                    Que.append(ret[i][1])
        
    for i in range(len(ret)):
        if chk[ret[i][1]] - chk[ret[i][0]] != ret[i][2]:
            return 0
        if chk[i] > M:
            return 0
    else:
        if ans < S:
            ans = S


def dfs(k):
    global check
    if k == Q-1:
        for i in range(2):
            check[k] = i
            g()
    else:
        for i in range(2):
            check[k] = i
            dfs(k+1)


dfs(0)
print(ans)

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

    A = iterate_A(A)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from itertools import combinations

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

D = defaultdict(set)
for a, b, c, d in ABCD:
  D[b-1].add((a-1, c, d))

for j in range(N-1, 0, -1):
  for x, y in combinations(D[j], 2):
    if x[0] == y[0]:
      continue
    if x[0] > y[0]:
      x, y = y, x
    if x[1] > y[1]:
      D[y[0]].add((x[0], x[1] - y[1], 0))

for i, j in combinations(range(N), 2):
  D[j].add((i, 0, 0))

que = deque([([1], 0)])
ans = 0
ans_L = []
while que:
  L, score = que.popleft()
  if len(L) == N:
    if score > ans:
      ans = score
      ans_L = L
  else:
    for a, c, d in D[len(L)]:
      l = L[a] + c
      if l <= M:
        que.append((L + [l], score + sum(d for a, c, d in D[len(L)] if l - L[a] == c)))
print(ans)

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 = [1]
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(1, m+1):
    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]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Time Limit Exceeded

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

A_full = np.arange(1,M+1)

l_tensu = [0]
for subset in itertools.combinations_with_replacement(A_full, N):
    tensu = 0

    A = np.sort(list(subset))
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    l_tensu.append(tensu)
    
print(max(l_tensu))

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())))
ans = 0
per_lst = []
def make_per(lst, n, m):
    n_lst = lst.copy()
    n_lst.append(0)
    if n == 1:
        for i in range(1, m+1):
            n_lst = n_lst.copy()
            n_lst[-1] = i
            if len(n_lst) > 1:
                if i >= n_lst[-2]:
                    per_lst.append(n_lst)
            else:
                per_lst.append(n_lst)
    else:
        for i in range(1, m+1):
            n_lst[-1] = i
            if len(n_lst) > 1:
                if i >= n_lst[-2]:
                    make_per(n_lst, n-1, m)
            else:
                make_per(n_lst, n-1, m)

make_per([], N, M)
# for i in per_lst:
#     print(i)
maxi = 0
for per in per_lst:
    score = 0
    for i in range(Q):
        a, b, c, d = abcd[i][0], abcd[i][1], abcd[i][2], abcd[i][3]
        a -= 1
        b -= 1
        if (per[b] - per[a]) == c: score += d
    if score > maxi: maxi = score
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
import itertools
l = []
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()])

for i in range(1,m+1):
    l.append(str(i))
a = list(itertools.combinations_with_replacement(l, n))

for k in range(len(a)): 
    for i in range(q):
        if int(a[k][c[i][1]-1]) - int(a[k][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:
#create date: 2020-05-02 21:28

import sys
stdin = sys.stdin
from itertools import product

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m, q = na()
    l = list()
    for i in range(q):
        l.append(na())
    ans = 0
    for switch in product(range(1, m+1), repeat=n):
        switch = list(switch)
        switch.sort()
        s = switch
        cnt = 0
        for a, b, c, d in l:
            a -= 1
            b -= 1
            if s[b] - s[a] ==c:
                cnt += d
        ans = max(cnt, ans)
    print(ans)

if __name__ == "__main__":
    main()

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

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
# 10進数のnを2進数のリストに変換
def n2kdigit(n,k):
    digits = []
    before = 0
    while n > 0:
        if before > n % k:
            return None
        digits.append(n % k)
        before = n % k
        n = n // k
    if len(digits) < N:
        return None

    return digits

ans = -1
for i in range(M ** (N)):
    A = n2kdigit(i, M)
    if A is not None:
        ans = max(ans, cal_ans(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())
X = [list(map(int, input().split())) for _ in range(Q)]
List = sorted(X)  
ans = 0
for i in range(2**Q):
  sum = 0
  A = [0 for _ in range(N)]
  for j in range(Q):
    if ((i >> j) & 1) and A[List[j][0]-1] != 0 and A[List[j][1]-1] != 0: #値入ってる
      if A[List[j][1]-1] - A[List[j][0]-1] == List[j][2]:
        sum += List[j][3]
      else:
        break
    elif ((i >> j) & 1) and A[List[j][0]-1] != 0 and A[List[j][1]-1] == 0: #aだけ値入ってる
      A[List[j][1]-1] = A[List[j][0]-1] + List[j][2] #値決める
      if A[List[j][1]-1] > M:
        break
      else:
        sum += List[j][3]
    elif ((i >> j) & 1) and A[List[j][0]-1] == 0 and A[List[j][1]-1] == 0: #値入ってない
      A[List[j][0]-1] = 1
      A[List[j][1]-1] = 1 + List[j][2] #値決める
      sum += List[j][3]
  else:
    if ans < sum:
      ans = sum
print(ans)

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
while A is not None:
    # print(A)
    score = get_score(A)
    if score > max_score:
        # print(A, score)
        max_score = score

    A = iterate_A(A)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

answer = 0

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

for balls in itertools.combinations_with_replacement(nums, N):
    score = 0
    for i in range(Q):
        test = list(balls)
        if test[abcd[i][0]-1] + abcd[i][2] == test[abcd[i][1]-1]:
            score += abcd[i][3]
    if score > answer:
        answer = score

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
b = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
import itertools
a = []
for i in range(1, M+1):
    for _ in range(N):
        a.append(i)
for set_A in itertools.combinations(a, N):
    A = list(set_A)
    n = 0
    for i in range(Q):
        if A[b[i][1]-1] - A[b[i][0]-1] == b[i][2]:
            n += b[i][3]
    ans = max(ans, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
# N, M, Q = 4, 6, 10

Qi = np.zeros((Q, 4), dtype='int64')
# Qi = np.zeros((Q, 4))

# listSample = []
# listSample.append("2 4 1 86568")
# listSample.append("1 4 0 90629")
# listSample.append("2 3 0 90310")
# listSample.append("3 4 1 29211")
# listSample.append("3 4 3 78537")
# listSample.append("3 4 2 8580")
# listSample.append("1 2 1 96263")
# listSample.append("1 4 2 2156")
# listSample.append("1 2 0 94325")
# listSample.append("1 4 3 94328")



for i in range(Q):
    Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,input().split())
    
# for i in range(Q):
#     Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,listSample[i].split())

# Qi[0][0], Qi[0][1], Qi[0][2], Qi[0][3] = map(int,"1 3 3 100".split())
# Qi[1][0], Qi[1][1], Qi[1][2], Qi[1][3] = map(int,"1 2 2 10".split())
# Qi[2][0], Qi[2][1], Qi[2][2], Qi[2][3] = map(int,"2 3 2 10".split())


Mi = np.arange(1, M+1)
maxD = 0
for listMi in (list(combinations_with_replacement(Mi, N))):
    d = 0
    for i in range(Q):
        # if (int(listMi[int(Qi[i][1]-1)]-listMi[int(Qi[i][0]-1)]) == int(Qi[i][2])):
        if (listMi[Qi[i][1]-1]-listMi[Qi[i][0]-1] == Qi[i][2]):
            d += Qi[i][3]
    if d>maxD:
        maxD = d
        # print (listMi)
print (int(maxD))

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([i])

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

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - 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:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
n, m, q = list(map(int, input().split()))
a, b, c, d = [0] * q, [0] * q, [0] * q, [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split()))
# Aは単調増加数列でNこの要素を持って最大でもMまで
ans = 0
locked_index = []
# dp = [0]*q
# dp[0] = d[0]
# for i in range(1, q):
#     # 普通に追加できるとき
#     if(a[i] in locked_index and b[i] in locked_index):

#     dp[i] = dp[i-1] + d[i]
#     locked_index.append(a[i])
#     locked_index.append(b[i])

max_point = 0

for i in range(2 ** q):
    ok_flg = True
    point = 0
    A = [1]*(n+1)
    locked_index = []
    saiyou = []
    for j in range(q):
        if ((i >> j) & 1):
            point += d[j]
            saiyou.append(j)
            A[b[j]] = A[a[j]] + c[j]
            if ((A[b[j]] > m)):
                ok_flg = False
                break
    # if(point == 357500):

    # ここで最終チェック
    for j in saiyou:
        if (A[b[j]] != A[a[j]] + c[j]):
            ok_flg = False

    # print(A, '\n', point)
    # print(saiyou)
    # print('==============')
    if max_point < point and ok_flg:
        max_point = point
print(max_point)
# A[b[i]] - A[a[i]] == c[i]

Submission status: Time Limit Exceeded

Solution code:
def ite(N, M):
    import itertools
    data = list(range(1, M+1, 1))
    return list(itertools.product(data, repeat=N))
  
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

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

m_s = 0
li2 = ite(N, M) 
for l2 in li2:
    if check(l2):
        s = score(l2, li)
        if m_s < s:
            m_s = s
            
print(m_s)

Submission status: Time Limit Exceeded

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

for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if ai < 1 or N < ai or bi < 1 or N < bi:
      continue
    if A[bi-1]-A[ai-1] == List[i][2]:
      point += List[i][3]
  if Max < point:
    Max = point

print(Max)

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

    #k = int(input())
    lists = []

    for i in range(m):
      for j in range(n):
         lists.append(int(i+1))
    
    lists = list(combinations_with_replacement(lists,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:
conditions = input().split(' ')
n = int(conditions[0])
m = int(conditions[1])
q = int(conditions[2])

data = [input().split(' ') for _ in range(q)]

def next_dim(dl, max_val):
    l = len(dl)
    output_list = []
    for i in range(l):
        for j in range(dl[i][-1], max_val + 1):
            buf_list = dl[i].copy()
            buf_list.append(j)
            output_list.append(buf_list)
    return output_list

a_list =[[i] for i in range(1, m + 1)]
for _ in range(n - 1):
    a_list = next_dim(a_list, m)

max_score = 0
for a in a_list:
    a_score = 0
    for i in range(q):
        num_1 = int(data[i][0]) - 1
        num_2 = int(data[i][1]) - 1
        diff = int(data[i][2])
        add_score = int(data[i][3])
        if a[num_2] - a[num_1] == diff:
            a_score += add_score
    if a_score > max_score:
        max_score = a_score
    
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

answer = 0

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

for balls in itertools.combinations_with_replacement(nums, N):
    score = 0
    for i in range(Q):
        test = sorted(list(balls))
        if test[abcd[i][0]-1] + abcd[i][2] == test[abcd[i][1]-1]:
            score += abcd[i][3]
    if score > answer:
        answer = score

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product

n, m, q = map(int, input().split())
a = [0 for _ in range(q)]
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
d = [0 for _ in range(q)]

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

max_score = 0
all_combs = product(range(1, m+1), repeat=n)
for comb in all_combs:
	is_sorted = True
	for i in range(1, n):
		if comb[i] - comb[i-1] < 0:
			is_sorted = False
			break
	if is_sorted:
		# print(comb)
		cur_score = 0
		for i in range(q):
			if comb[b[i]] - comb[a[i]] == c[i]:
				cur_score += d[i]
		# print("cur_score", cur_score)
		if cur_score > max_score:
			max_score = cur_score
			# print("new max", max_score)
		# print()

print(max_score)

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):
        vv.append(v)

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

ww = []
for i in combinations(vv,N):
    w  = []
    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 numpy as np
import sys
from itertools import combinations_with_replacement
input = sys.stdin.readline
N, M, Q = map(int, input().split())
# N, M, Q = 4, 6, 10

Qi = np.zeros((Q, 4))

# listSample = []
# listSample.append("2 4 1 86568")
# listSample.append("1 4 0 90629")
# listSample.append("2 3 0 90310")
# listSample.append("3 4 1 29211")
# listSample.append("3 4 3 78537")
# listSample.append("3 4 2 8580")
# listSample.append("1 2 1 96263")
# listSample.append("1 4 2 2156")
# listSample.append("1 2 0 94325")
# listSample.append("1 4 3 94328")



for i in range(Q):
    Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,input().split())
    
# for i in range(Q):
    # Qi[i][0], Qi[i][1], Qi[i][2], Qi[i][3] = map(int,listSample[i].split())

# Qi[0][0], Qi[0][1], Qi[0][2], Qi[0][3] = map(int,"1 3 3 100".split())
# Qi[1][0], Qi[1][1], Qi[1][2], Qi[1][3] = map(int,"1 2 2 10".split())
# Qi[2][0], Qi[2][1], Qi[2][2], Qi[2][3] = map(int,"2 3 2 10".split())


Mi = np.arange(1, M+1)
maxD = 0
for listMi in (list(combinations_with_replacement(Mi, N))):
    d = 0
    for i in range(Q):
        if (int(listMi[int(Qi[i][1]-1)]-listMi[int(Qi[i][0]-1)]) == int(Qi[i][2])):
            d += Qi[i][3]
    if d>maxD:
        maxD = d
print (int(maxD))