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:
import numpy as np
import itertools
n, m, q = [int(a) for a in input().split()]
a = []
b = []
c = []
d = []
for i in range(q):
    a_,b_,c_,d_ = [int(a) for a in input().split()]
    a.append(a_)
    b.append(b_)
    c.append(c_)
    d.append(d_)

a = np.asarray(a) - 1
b = np.asarray(b) - 1
c = np.asarray(c)
d = np.asarray(d)

ans = 0

for A in itertools.combinations_with_replacement(range(m), n):
    ans_ = 0
    for i in range(q):
        if A[b[i]] - A[a[i]] == c[i]:
            ans_ += d[i]
    if ans_ > ans:
        ans = ans_

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

pat = list(product(range(1,M+1),repeat=N))
pat_sort = list(map(lambda pati: sorted(pati),pat))
pat_uni = list(map(list, set(map(tuple, pat_sort))))

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

def ans(A, M):
    lista = []
    l = len(A)
    for i in range(0,len(A)):
        for j in range(A[i][-1], M+1):
            listb = A[i].copy()
            listb.append(j)
            A.append(listb)
    A = A[l:]
    return A

B = []
for i in range(Q):
    lista = list(map(int,input().split()))
    B.append(lista)
    
maxSum = 0

A = [[i] for i in range(1,N+1)]
for i in range(N):
    A = ans(A, M)

for As in A:
    Sum = 0
    for i in range(Q):
        if As[B[i][1]] - As[B[i][0]] == B[i][2]:
            Sum += B[i][3]
        
    maxSum = max(maxSum, Sum)

print(maxSum)

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

ans = 0
P = [[i for i in range(1, M+1)] for _ in range(N)]

# print(R)
for comb in itertools.product(*P):
    flag = True
    p = comb[0]
    for i in comb:
        if i < p:
            flag = False
            break
        p = i

    if not flag:
        continue

    # print(comb)

    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

print(ans)

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
import numpy as np
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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n,m,q = map(int,input().split())
E = [list(map(int,input().split())) for i in range(q)]
def dfs(l,string):
  global ans
  if l == n: ans = max(ans,check(string));return
  for i in range(int(string[-1]),m+1):
    dfs(l+1,string+str(i))

def check(string):
  re = 0
  for a,b,c,d in E:
    if int(string[b])-int(string[a]) == c:
      re += d
  return re
dfs(0,"1")
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


def main():
    n, m, q = map(int, input().split(" "))
    abcds = [list(map(int, input().split(" "))) for i in range(q)]

    A = [1 for i in range(n)]
    for k in range(m-1):
        A.extend([k+2 for i in range(n)])

    #print(A)

    ls = list(set(list(itertools.combinations(A, n))))
    #print(ls)
    points = np.zeros(len(ls))
    for j in range(len(ls)):
        A = ls[j]
        for i in range(q):
            ary = abcds[i]
            if A[ary[1]-1] == A[ary[0]-1] + ary[2]:
                points[j] += ary[3]


    print(int(np.max(points)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m, q = list(map(int, input().split(' ')))
a = np.zeros((q,), dtype=np.int)
b = np.zeros((q,), dtype=np.int)
c = np.zeros((q,), dtype=np.int)
d = np.zeros((q,), dtype=np.int)
for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split(' ')))
a -= 1
b -= 1

def calc_point(seq):
    point = 0
    for i in range(q):
        if seq[b[i]] - seq[a[i]] == c[i]:
            point += d[i]
    return point

def search_max_point(depth, seq):
    if depth == n:
        return calc_point(seq)
    if depth == 0:
        num_start = 1
    else:
        num_start = seq[depth-1]
    max_point = 0
    for num in range(num_start, m+1):
        child_seq = seq.copy()
        child_seq[depth] = num
        child_point = search_max_point(depth+1, child_seq)
        if child_point > max_point:
            max_point = child_point
    return max_point

ans = search_max_point(0, np.zeros((n,), dtype=np.int))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
input = stdin.readline

setrecursionlimit(10 ** 9)

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

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

A = []


def make(tmp):
    if len(tmp) >= 2 * N:
        A.append(list(map(int, tmp.split())))
        return
    else:
        for j in range(int(tmp[len(tmp) - 2]), M + 1):
            make(tmp + str(j) + " ")


for i in range(1, M + 1):
    tmp = ""
    tmp += str(i)
    tmp += " "
    make(tmp)

ans = 0

for s in A:
    num = 0
    for q in range(Q):
        a, b, c, d = abcd[q]
        if s[b - 1] - s[a - 1] == c:
            num += d
    ans = max(ans, num)

print(ans)

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())))
abcd.sort()

import itertools
LIST = []
for i in range(1,M+1):
    LIST.extend([i for j in range(N)])
A = list(itertools.combinations(LIST,N))
# print(A)
ans = 0
for item in A:
    tmp = 0
    for req in abcd:
        if item[req[1]-1] - item[req[0]-1] == req[2]:
            tmp+= req[3]
    ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
N, M, Q=map(int, input().split())
s = [input().split() for i in range(Q)]
A = list(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:
# 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 = []

all = 0
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
    all += d

abcd = sorted(abcd, key= lambda x:x[3], reverse= True)
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(ans, A):
    tmp = 0
    tmp_all = copy.deepcopy(all)
    for i in range(Q):
        a, b, c, d = abcd[i]
        tmp_all -= d
        if A[b] - A[a] == c:
            tmp += d
        else:
            if tmp_all + tmp <= ans:
                return ans
    ans = max(ans, tmp)
    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) < 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 = cal_ans(ans, [int(i) for i in A])
print(ans)

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
    ll = [k for k in l if k != -1]
    if 1<=min(ll) and max(ll)<=m:
          x=copy.deepcopy(ll)
          x.sort()
          if x==ll and point>s:
            s=point
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
import time



"""
def make_table_min(n, m):
    Table = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    c = 10
    for i in range(n):
        rem = np.random.randint(1,m+1)
        Table.remove(rem)
    return Table

"""

def make_table(n, m):
    Table = [None]*n
    for i in range(n):
        rem = np.random.randint(1,m+1)
        Table[i] = rem
    return Table

t0 = time.time()
n, m, q = map(int, input().split())
Lis = [[int(e) for e in input().split()] for _ in range(q)]

Sum_cor = []
for i in range(10000000000):
    if m >=6:
        Table = make_table(n,m)
    else:
        Table = make_table(n,m)
    Table.sort()
    d_sum = 0
    for l in Lis:
        if Table[l[1]-1]-Table[l[0]-1] == l[2]:
            d_sum+=l[3]
    Sum_cor.append(d_sum)
    t1 = time.time()
    if t1-t0 >1.9:
        print(max(Sum_cor))
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m,q=MI()
strs=[[[] for i in range(m)] for i in range(n)]
for i in range(m):
    strs[0][i].append(str(i))
#print(strs)
for i in range(n-1):
    for j in range(m):
        for k in range(j,m):
            for s in strs[i][k]:
                strs[i+1][j].append(str(j)+s)
#print(strs)

L=strs[n-1]
#print(L)
lis=[]
for i in range(m):
    for s in L[i]:
        lis.append(s)
#print(lis)
mx=0
zyou=[LI() for i in range(q)]
for u in lis:
    po=0
    for k in range(q):
        a,b,c,d=zyou[k]
        if int(u[b-1])-int(u[a-1])==c:
            po+=d
    if po>mx:
        mx=po
print(mx)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n,m,q=map(int,input().split())
l=[]
fa=[m]*n

def check_list(la: list):
    for i in range(len(la)-1):
        if la[i+1]<la[i] or la[i]>m or la[i]<1:
            return False
    
    return True


def dfs(i,a):
    if not check_list(a):
        return -1
    elif i==len(l):
        ret=0
        for i in range(len(a)-1):
            if a[i+1]<a[i] or a[i]>m:
                ret=-1

        for le in l:
            if a[le[1]-1]-a[le[0]-1]==le[2]:
                ret+=le[3]
        return ret
    else:
        c0=a.copy()     # use this (change first)
        c1=a.copy()     # use this (change second)
        c2=a.copy()     # dojn't use this
        c0[l[i][0]-1]=c0[l[i][1]-1]-l[i][2]
        c1[l[i][1]-1]=c1[l[i][0]-1]+l[i][2]
        return max(dfs(i+1,c0),dfs(i+1,c1),dfs(i+1,c2))




for _ in range(q):
    l.append(tuple(map(int,input().split())))


print(dfs(0,fa))

Submission status: Time Limit Exceeded

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

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

def judge(l):
    cv=[1 for h in range(n)]
    for i in range(q):
        if l[i]==1:
            cv[t[i][1]]=cv[t[i][0]]+t[i][2]
    for i in range(n):
        if cv[i]>m:
            return False
    for i in range(q):
        if l[i]==1:
            if cv[t[i][1]]-cv[t[i][0]]!=t[i][2]:
                return False
    return True

num=[0,1]
ans=0

for df in itertools.product(num,repeat=q):
    ty=list(df)
    if judge(ty):
        to=0

        for i in range(q):
            if ty[i]==1:
                to+=t[i][3]
        ans=max(ans,to)

print(ans)

Submission status: Time Limit Exceeded

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

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

def judge(l):
    cv=[1 for h in range(n)]
    for i in range(q):
        if l[i]==1:
            cv[t[i][1]]=cv[t[i][0]]+t[i][2]
    for i in range(n):
        if cv[i]>m:
            return False
    for i in range(q):
        if l[i]==1:
            if cv[t[i][1]]-cv[t[i][0]]!=t[i][2]:
                return False
    return True

num=[0,1]
ans=0

for df in itertools.product(num,repeat=q):
    ty=list(df)
    if judge(ty):
        to=0

        for i in range(q):
            if ty[i]==1:
                to+=t[i][3]
        ans=max(ans,to)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
N, M, Q=map(int, input().split())
s = [input().split() for i in range(Q)]
A = list(combinations_with_replacement(range(1,M+1), N))
kotae=0
high_kotae=0
for i in range(len(A)):
    kotae=0
    A2=A[i]
    for j in range(Q):
        if A2[int(s[j][1])-1]-A2[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 itertools

N,M,Q = map(int, input().split())
a=[]
ind_add = []
sum_n = 0
for _ in range(Q):
  tmp = list(map(int, input().split()))
  a.append(tmp)
  ind_add.append(tmp[0])
  ind_add.append(tmp[1])
  sum_n += tmp[3]

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

  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
    if n == sum_n:
      break

print(n)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

_, m, q = list(map(int, input().split(" ")))
abcd = [list(map(int, input().split(" "))) for _ in range(q)]
max_point = 0
n = max([a[1] for a in abcd])
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  itertools
n,m,q=map(int,input().split())

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

def judge(l):
    cv=[1 for h in range(n)]
    for i in range(q):
        if l[i]==1:
            cv[t[i][1]]=cv[t[i][0]]+t[i][2]
    flag=True
    for i in range(n):
        if cv[i]>m:
            flag= False

    for i in range(q):
        if l[i]==1:
            if cv[t[i][1]]-cv[t[i][0]]!=t[i][2]:
                flag=False
    if flag:
        return True
    else:
        return False

num=[0,1]
ans=0

for df in itertools.product(num,repeat=q):
    ty=list(df)
    if judge(ty):
        to=0
        #print(ty)
        for i in range(q):
            if ty[i]==1:
                to+=t[i][3]

        ans=max(ans,to)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from itertools import combinations_with_replacement

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

x = [_ for _ in range(1, M+1)]
#y = list(combinations(x, N))
y = list(combinations_with_replacement(x, N))

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement as AAA
N, M, Q=map(int, input().split())
s = [input().split() for i in range(Q)]
A = list(AAA(range(1,M+1), N))
kotae=0
high_kotae=0
for i in range(len(A)):
    kotae=0
    A2=A[i]
    for j in range(Q):
        if A2[int(s[j][1])-1]-A2[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 copy
N, M, Q = [eval(v) for v in input().strip().split(" ")]

a_list, b_list, c_list, d_list = [], [], [], []

for k in range(Q):
    a, b, c, d = [eval(v) for v in input().strip().split(" ")]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

max_value = 0

def calc_score(complete_A):
    score = 0
    for i in range(Q):
        if complete_A[b_list[i]] - complete_A[a_list[i]] == c_list[i]:
            score += d_list[i]
    return score

def search(A, M, depth, a_list, b_list, c_list, d_list, max_value, count):
    # print("%s: %s" % (depth, A))
    # count += 1
    # if count > 20:
    #     exit(0)
    if depth > 0:
        last_A = A[-1]
        for k in range(last_A, M + 1):
            next_A = copy.deepcopy(A)
            next_A.append(k)
            max_value = search(next_A, M, depth - 1, a_list, b_list, c_list, d_list, max_value, count)
    else:
        value = calc_score(A[1:])
        if value > max_value:
            max_value = value
    return max_value

count = 0
A = [1]
print(search(A, M, N + 1, a_list, b_list, c_list, d_list, max_value, count))

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([1, 0], repeat=q):
    cnt = 0
    aaa = []
    aaaa = []
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
            cnt += d
    if ans < cnt:
        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 not flag:
                    cnt = 0
                    break
        if ans < cnt:
            ans = cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n,m,q=map(int,input().split())
l=[]
fa=[m]*n

def check_list(la: list):
    for i in range(len(la)-1):
        if la[i+1]<la[i] or la[i]>m or la[i]<1:
            return False
    
    return True


def dfs(i,a):
    if not check_list(a):
        return -1
    elif i==len(l):
        ret=0
        for i in range(len(a)-1):
            if a[i+1]<a[i] or a[i]>m:
                ret=-1

        for le in l:
            if a[le[1]-1]-a[le[0]-1]==le[2]:
                ret+=le[3]
        return ret
    else:
        c0=a.copy()     # use this (change first)
        c1=a.copy()     # use this (change second)
        c2=a.copy()     # dojn't use this
        c0[l[i][0]-1]=c0[l[i][1]-1]-l[i][2]
        c1[l[i][1]-1]=c1[l[i][0]-1]+l[i][2]
        return max(dfs(i+1,c0),dfs(i+1,c1),dfs(i+1,c2))




for _ in range(q):
    l.append(tuple(map(int,input().split())))

l.sort(key=lambda x:x[3],reverse=True)

print(dfs(0,fa))

Submission status: Time Limit Exceeded

Solution code:
import copy

n,m,q = map(int,input().split())
p = [input().split() for i in range(q)]
#和がm-1以下となるn個のリストを列挙する
global samples
samples= []
def rekkyo(M, N, lists,maxlen):
    if N>0:
        for i in range(M):
            lists.append(i)
            if len(lists) == maxlen:
                samples.append(copy.copy(lists))
            else:
                rekkyo(M-i,N-1,lists,maxlen)
            lists.pop(-1)

rekkyo(m,n,[],n)
ans = 0
for i in samples:
    tmp=0
    for j in p:
        if sum(i[int(j[0]):int(j[1])]) == int(j[2]):
            tmp+=int(j[3])
    if ans<tmp:
        ans=tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
maxscore = sum([row[3] for row in matrix])
for i in itertools.product(range(1,M+1), repeat=N):
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore
    if ansscore == maxscore:
        break
print(ansscore)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m, q = list(map(int, input().split(' ')))
a = np.zeros((q,), dtype=np.int)
b = np.zeros((q,), dtype=np.int)
c = np.zeros((q,), dtype=np.int)
d = np.zeros((q,), dtype=np.int)
for i in range(q):
    a[i], b[i], c[i], d[i] = list(map(int, input().split(' ')))
a -= 1
b -= 1

def calc_point(seq):
    point = 0
    for i in range(q):
        try:
            if seq[b[i]] - seq[a[i]] == c[i]:
                point += d[i]
        except:
            print(b[i], a[i], c[i])
    return point

def search_max_point(depth, seq):
    if depth == n:
        return calc_point(seq)
    if depth == 0:
        num_start = 1
    else:
        num_start = seq[depth-1]
    max_point = 0
    for num in range(num_start, m+1):
        child_seq = seq.copy()
        child_seq[depth] = num
        child_point = search_max_point(depth+1, child_seq)
        if child_point > max_point:
            max_point = child_point
    return max_point

ans = search_max_point(0, np.zeros((n,), dtype=np.int))
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())

suma = sum([int(aa[3]) for aa in a])

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_
        if ans == suma:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[n,m,q] = list(map(int,input().split(" ")))
a = []
for i in range (q):
    a.append(list(map(int,input().split(" "))))
ans = 0
for i in range (10**n):
    tmp = 0
    nlst = [1 for t in range(n)]
    for j in range (len(str(i))):
        nlst[j]=int(str(i)[j])+1
    if max(nlst)<=m:
        nlst.sort()
        for k in range(q):
            a_ = a[k][0]
            b_ = a[k][1]
            c_ = a[k][2]
            d_ = a[k][3]
            if nlst[b_-1]-nlst[a_-1]==c_:
                tmp = tmp + d_
        if ans < tmp:
            ans = tmp
    
print(ans)

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(''.join([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:
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(dict)
for a, b, c, d in ABCD:
  D[b-1][(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]:
      if (x[0], x[1] - y[1]) not in D[y[0]]:
        D[y[0]][(x[0], x[1] - y[1])] = 0

for j in range(1, N):
  if (j-1, 0) not in D[j]:
    D[j][(j-1, 0)] = 0

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

Submission status: Time Limit Exceeded

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

a = [list(map(int, input().split())) for i in range(q)]
seq=[]
for j in range(1,m+1):
  sea=[j]*n
  seq=seq+sea
ddd=list(itertools.combinations(seq, n))
y=0
ppp=[]
for c in ddd:
  for b in a:
    if c[b[1]-1]-c[b[0]-1]==b[2]:
      y+=b[3]
  ppp.append(y)
  y=0
p2=sorted(ppp)
print(p2[-1])

Submission status: Time Limit Exceeded

Solution code:
import copy

n,m,q = map(int,input().split())
p = [input().split() for i in range(q)]
#和がm-1以下となるn個のリストを列挙する
global samples
samples= []
def rekkyo(M, N, lists,maxlen):
    if N>0:
        for i in range(M):
            lists.append(i)
            if len(lists) == maxlen:
                samples.append(copy.copy(lists))
            rekkyo(M-i,N-1,lists,maxlen)
            lists.pop(-1)

rekkyo(m,n,[],n)
ans = 0
for i in samples:
    tmp=0
    for j in p:
        if sum(i[int(j[0]):int(j[1])]) == int(j[2]):
            tmp+=int(j[3])
    if ans<tmp:
        ans=tmp

print(ans)

Submission status: Time Limit Exceeded

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

s = [1] * n
#st[b[i]] - st[a[i]]  = c[i]
num = n-1
ans1 = [0] * 100000000
ans = 0
t = 0

while(s[0] != m):

    for i in range(q):
        if s[b[i]-1] - s[a[i]-1]  == c[i]:
            ans += d[i]
    #print(s)
    #print(ans)

    ans1[t] = ans
    t += 1

    ans = 0

    if s[num] < m:
        s[num] += 1
    elif num > 0 :
        num -= 1
        temp = s[num]+1
        if temp < m:
            for i in range(num,n):
                s[i] = temp
        else:
            while(s[num] == m):
                num -= 1
            temp = s[num]+1
            for i in range(num,n):
                s[i] = temp

        num = n-1






print(max(ans1))