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: Runtime Error

Solution code:
import sys
from itertools import combinations_with_replacement
from numba import njit


@njit('(i8,i8,i8[:,:])')
def solve(n, m, query):
    li = [0] * m
    for i in range(1, m + 1):
        li[i - 1] = i
    max_point: int = 0
    for a in combinations_with_replacement(li, n):
        point = 0
        for qer in query:
            if a[qer[1] - 1] - a[qer[0] - 1] == qer[2]:
                point += qer[3]
        if point > max_point:
            max_point = point
    print(max_point)


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    solve(n, m, query)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from itertools import combinations_with_replacement
from numba import njit


@njit('(i8,i8,i8[:,:])')
def solve(n, m, query):
    li = [i for i in range(1, m + 1)]
    max_point: int = 0
    for a in combinations_with_replacement(li, n):
        point = 0
        for qer in query:
            if a[qer[1] - 1] - a[qer[0] - 1] == qer[2]:
                point += qer[3]
        if point > max_point:
            max_point = point
    print(max_point)


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    query = [list(map(int, input().split())) for _ in range(q)]
    solve(n, m, query)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
int n, m, q;
vector<int> B; //一つ前の数字を代入しておく。
vector<int> tui(int u)
{
    vector<int> A(n);
    if (u == 0)
    {
        rep(i, n)
        {
            A[i] = 1;
        }
        B = A;
        return A;
    }
    int i = 0;
    if (B[n - 1 - i] != m)
    {
        B[n - 1 - i] += 1;
    }
    else if (B[n - 1 - i] == m)
    {
        for (int j = n - 2 - i; j >= 0; j--)
        {
            if (B[j] != m)
            {
                B[j] += 1;
                for (int h = j + 1; h < n; h++)
                {
                    B[h] = B[j];
                }
                break;
            }
        }
    }
    return B;
}
int main()
{
    cin >> n >> m >> q;
    //これから長さnで大きさm以下の数列を全て書き出す
    //最後まで行ったら最大値を返す。
    B.resize(n);
    vector<ll> a(q), b(q), c(q), d(q);
    rep(i, q)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    //生成しまくるまで
    vector<int> s(n);
    int i = 0;
    int flag = 0;
    ll max1 = 0;
    while (1)
    {
        ll count = 0;
        flag = 0;
        s = tui(i);
        /* for (int x : s)
        {
            cout << x;
        }*/

        rep(i, n)
        {
            if (s[i] != m)
            {
                flag = 1;
                break;
            }
        }
        rep(j, q)
        {
            if (s[b[j] - 1] - s[a[j] - 1] == c[j])
            {
                count += d[j];
            }
        }
        max1 = max(max1, count);
        if (flag == 0)
        {
            break;
        }
        i++;
    }
    cout << max1 << endl;
}

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
#下記の書き方応用できそうだ
arr = [list(map(int, input().split())) for _ in range(Q)]

ans = 0

"""
下記は問題の条件式をみて判断できる1<=M<=10
"""
for i1 in range(1, M+1):
    for i2 in range(i1, M+1):
        for i3 in range(i2, M+1):
            for i4 in range(i3, M+1):
                for i5 in range(i4, M+1):
                    for i6 in range(i5, M+1):
                        for i7 in range(i6, M+1):
                            for i8 in range(i7, M+1):
                                for i9 in range(i8, M+1):
                                    for i10 in range(i9, M+1):
                                        tmp = 0
                                        #添字の順番を合わせるために一つ目に0を代入している感じ。
                                        arrs = {0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10}
                                        for a, b, c, d in arr:
                                            if arrs[b] - arrs[a] == c:
                                                tmp += b
                                        ans = max(ans, tmp)
                            
print(ans)

Submission status: Runtime Error

Solution code:
for i1 in range(1, M+1):
    for i2 in range(i1, M+1):
        for i3 in range(i2, M+1):
            for i4 in range(i3, M+1):
                for i5 in range(i4, M+1):
                    for i6 in range(i5, M+1):
                        for i7 in range(i6, M+1):
                            for i8 in range(i7, M+1):
                                for i9 in range(i8, M+1):
                                    for i10 in range(i9, M+1):
                                        tmp = 0
                                        #添字の順番を合わせるために一つ目に0を代入している感じ。
                                        arrs = {0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10}
                                        for a, b, c, d in arr:
                                            if arrs[b] - arrs[a] == c:
                                                tmp += b
                                        ans = max(ans, tmp)
                            
print(ans)

Submission status: Runtime Error

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

a = []
ref = []
ans = 0

for i in range(Q):
  tmp = list(map(int, input().split()))
  ref.append(tmp)
  
#print("----tmp----")
#print(ref)

for i in range(1, M+1):
  for j in range(i, M+1):
    for k in range(j, M+1):
      a.append([i, j, k])

#print("---a---")
#print(a)

for i in a:
  sum = 0
  for j in ref:
    
    #print("---i, j---")
    #print(i, j)
    if i[j[1]-1]-i[j[0]-1] == j[2]:
      sum += j[3]
      #print("---sum---")
      #print(sum)
  
  if ans < sum:
    ans = sum
    
print(ans)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
vec = [list(map(int, input().split())) for i in range(Q)]
A = itertools.combinations_with_replacement(range(1,M+1), N)
ans = 0

for a in A:
    tmp = 0
    for v in vec:
        if (a[v[1]-1] - a[v[0]-1]) == v[2]:
            tmp += v[3]
    if ans < tmp:
        ans = tmp
        
print(ans)

Submission status: Runtime Error

Solution code:
N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []
dd = 0
for i in range(Q):
    t = list(map(int, input().split()))
    a.append(t[0])
    b.append(t[1])
    c.append(t[2])
    d.append(t[3])
    if t[1] - t[0] == t[3]:
        dd += t[4]

print(dd)

Submission status: Runtime Error

Solution code:
# 重複組み合わせの全列挙

import itertools

# n+m-1個からn個を選ぶ組み合わせ
n, m, q = map(int, input().split())
seq = list(range(n+m-1))
p = list(itertools.combinations(seq, n))

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

res = 0
for i in range(p):
    t = [0] * n
    pp = sorted(i)
    idx = 0
    for e in pp:
        t[idx] = 1 + e - idx
        idx += 1
    
    tmp = 0
    for j in range(q):
        if t[b[j]-1] - t[a[j]-1] == c[j]:
            tmp += d[j]
    
    res = max(res, tmp)

print(res)

Submission status: Runtime Error

Solution code:
import itertools

N,M,Q = map(int,input().split())
s = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
b_2 = []

for t in itertools.product(range(M+1), repeat=N):
  for a,b,c,d in s:
    if t[b-1]-t[a-1] == c:
      score += d
      ans = max(ans,score)
  score = 0
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import combinations as com
N,M,Q=map(int,input().split())
x=[list(map(int,input().split())) for i in range(Q)]
ans=[]
for A in com([range(1,M+1)],N):
  count=0
  for i in range(Q):
    if A[x[i][1]]-A[x[i][0]]==x[i][2]:
      count+=x[i][3]
  ans.append(count)
  
print(max(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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


#最初に全てのAペアを作ればいいだけだった
#1stepで何するか
#終了条件
ans = [0]
def dfs(A):
    if len(A) == N:
        tmp_ans = 0
        for ele in tmp
            if ele[1] - ele[0] == ele[2]:
                tmp_ans += ele[-1]
        ans[0] = max(tmp_ans,ans[0])

        return
    
    A_min = A[-1]
    while(1):
        if A_min > M:
            break
        A.append(A_min)
        dfs(A)
        A.pop()
        A_min += 1

for i in range(M):
    dfs([i+1])

print(ans[0])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def calc_score(A):
    score = 0
    for a, b, c, d in lists:
        if A[b -1] - A[a - 1] == c:
            score += d
    return score

def dfs(A):
    global ans
    if len(A) == N:
        score = calc_score(A)
        ans = max(score, ans)
        return
    for n in range(A[-1], M + 1):
        dfs(A + [n])
        
dfs([1])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
 
sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print('\n'.join(x))
 
x = ni()
v = 100
for i in range(1, 4000):
    v += v // 100
    if v >= x:
        print(i)
        break

Submission status: Runtime Error

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

abcd = [list(map(int, input().split())) for _ in range(q)]
from itertools import combinations_with_replacement as cwr
A = list(cwr(range(1, m+1), n))


maxPoint = 0
for item in A:
  point = 0
  for i in range(len(abcd)):
    a = abcd[i][0]
    b = abcd[i][1]
    c = abcd[i][2]
    d = abcd[i][3]
    if item[b-1] - item[a-1] == item[c-1]:
      point += d
  if point > maxPoint:
    maxPoint = point
print(maxPoint)

Submission status: Runtime Error

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

abcd = [list(map(int, input.split())) for _ in range(q)]
from itertools import combinations_with_replacement as cwr
A = list(cwr(range(1, m+1), n))


maxPoint = 0
for item in A:
  point = 0
  for i in range(len(abcd))
  a = abcd[i][0]
  b = abcd[i][1]
  c = abcd[i][2]
  d = abcd[i][3]
  if item[b-1] - item[a-1] == item[c-1]:
    point += d
  if point > maxPoint:
    maxPoint = point
print(maxPoint)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
abcd=[]
for i in range(Q):
    abcdabcd=list(map(int,input().split()))
    abcd.append(abcdabcd)
#入れるAはリスト、[]で表現
def cal(A):
    t=0
    for abcdi in abcd:
        a=abcdi[0]
        b=abcdi[1]
        c=abcdi[2]
        d=abcdi[3]
        if A[b-1]-A[a-1]==c:
            t+=d
    return t

maxi=0
for i in range(1,M+1):
    if M==1:
        maxi=max(maxi,cal([i]))
    for j in range(i,M+1):
        if M==2:
            maxi=max(maxi,cal([i,j]))
        for k in range(j,M+1):
            if M==3:
                maxi=max(maxi,cal([i,j,k]))
            for l in range(k,M+1):
                if M==4:
                    maxi=max(maxi,cal([i,j,k,l]))
                for m in range(l,M+1):
                    if M==5:
                        maxi=max(maxi,cal([i,j,k,l,m]))
                    for n in range(m,M+1):
                        if M==6:
                             maxi=max(maxi,cal([i,j,k,l,m,n]))
                        for o in range(n,M+1):
                            if M==7:
                                maxi=max(maxi,cal([i,j,k,l,m,n,o]))
                            for p in range(o,M+1):
                                if M==8:
                                    maxi=max(maxi,cal([i,j,k,l,m,n,o,p]))
                                for q in range(p,M+1):
                                    if M==9:
                                        maxi=max(maxi,cal([ij,k,l,m,n,o,p,q]))
                                    for r in range(q,M+1):
                                        if M==10:
                                            maxi=max(maxi,cal([i,j,k,l,m,n,o,p,q,r]))
                                        

print(maxi)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
abcd=[]
for i in range(Q):
    abcdabcd=list(map(int,input().split()))
    abcd.append(abcdabcd)
#入れるAはリスト、[]で表現
def cal(A):
    t=0
    for abcdi in abcd:
        a=abcdi[0]
        b=abcdi[1]
        c=abcdi[2]
        d=abcdi[3]
        if A[b-1]-A[a-1]==c:
            t+=d
    return t

maxi=0
for i in range(1,M+1):
    if M==1:
        maxi=max(maxi,cal([i]))
    for j in range(i,M+1):
        if M==2:
            maxi=max(maxi,cal([i,k]))
        for k in range(j,M+1):
            if M==3:
                maxi=max(maxi,cal([i,j,k]))
            for l in range(k,M+1):
                if M==4:
                    maxi=max(maxi,cal([i,j,k,l]))
                for m in range(l,M+1):
                    if M==5:
                        maxi=max(maxi,cal([i,j,k,l,m]))
                    for n in range(m,M+1):
                        if M==6:
                             maxi=max(maxi,cal([i,j,k,l,m,n]))
                        for o in range(n,M+1):
                            if M==7:
                                maxi=max(maxi,cal([i,j,k,l,m,n,o]))
                            for p in range(o,M+1):
                                if M==8:
                                    maxi=max(maxi,cal([i,j,k,l,m,n,o,p]))
                                for q in range(p,M+1):
                                    if M==9:
                                        maxi=max(maxi,cal([ij,k,l,m,n,o,p,q]))
                                    for r in range(q,M+1):
                                        if M==10:
                                            maxi=max(maxi,cal([i,j,k,l,m,n,o,p,q,r]))
                                        

print(maxi)

Submission status: Runtime Error

Solution code:
n, m, q = [int(e) for e in input().split()]

import itertools as it
abcd=list()
for i in range(q):
    abcd.append([int(e) for e in input().split()])


all = it.combinations(range(1,m+1),n)

count=list()
num=0
for i in all:
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            num += j[3]
        else:
            pass
    count.append(num)
    num=0



print(max(count))

Submission status: Runtime Error

Solution code:
# 全通りを計算する
# collectins.conbination 1-19，len = 19の配列用意
# その中から9個選ぶ
# それぞれの選ばれたものを仕切りと考え，左の仕切りから順に1~10まで数える．
# それらを配列とみなす．
# それで全探索し，最も得点が高いものの組み合わせが答え
# 19C9 は3万程度なのでOK

import itertools


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

    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)
    ans = 0
    length = 19
    for item in itertools.combinations(range(length), m-1):
        ptn = []
        num = 1
        p = 0
        for i in range(length):
            if i == item[p]:
                num += 1
                p += 1
                p = min(m-2, p)
                continue
            ptn.append(num)
        tmp = 0
        for k in range(q):
            if (ptn[B[k]-1] - ptn[A[k]-1]) == C[k]:
                tmp += D[k]

        ans = max(tmp, ans)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import itertools


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

    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)
    ans = 0
    length = m+n-1
    for item in itertools.combinations(range(length), m-1):
        ptn = []
        num = 1
        p = 0
        for i in range(length):
            if i == item[p]:
                num += 1
                p += 1
                p = min(m-2, p)
                continue
            ptn.append(num)
        tmp = 0
        for k in range(q):
            if (ptn[B[k]-1] - ptn[A[k]-1]) == C[k]:
                tmp += D[k]
            else:
                tmp += 0

        ans = max(tmp, ans)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import itertools


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

    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)
    ans = 0
    length = m+n-1
    for item in itertools.combinations(range(length), m-1):
        ptn = []
        num = 1
        p = 0
        for i in range(length):
            if i == item[p]:
                num += 1
                p += 1
                p = min(m-2, p)
                continue
            ptn.append(num)
        tmp = 0
        for k in range(q):
            if (ptn[B[k]-1] - ptn[A[k]-1]) == C[k]:
                tmp += D[k]

        ans = max(tmp, ans)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import itertools


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

    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)
    ans = 0
    for item in itertools.combinations(range(19), 9):
        ptn = []
        num = 1
        p = 0
        for i in range(19):
            if i == item[p]:
                num += 1
                p += 1
                p = min(8, p)
                continue
            ptn.append(num)
        tmp = 0
        for k in range(q):
            if (ptn[B[k]] - ptn[A[k]]) == C[k]:
                tmp += D[k]

        ans = max(tmp, ans)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
# ここから入力
from itertools import combinations_with_replacement
n, m, q = map(int, input().split())
lst = []
for i in range(q):
    a = list(map(int, input().split()))
    lst.append(a)
# ここまで入力
x = 0
# 重複組合せ
for i in combinations_with_replacement(range(1, m + 1), n):
    s = 0
    for j in a:
        if i[j[1] - 1] - i[j[0] - 1] == j[2]:
            s += j[3]
    if x < s:
        x = s
print(x)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import itertools.combinations_with_replacement
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from itertools import itertools_with_replacement
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

Submission status: Runtime Error

Solution code:
import sys, math, copy
import numpy as np
sys.setrecursionlimit(10**7)

def returnDepth(node):
    return math.floor(math.log2(node + 1))

def isContradicting(matrix):
    coefMatrix = [[0] * n for i in range(len(matrix))]
    coefMatrix2 = [[0] * (n+1) for i in range(len(matrix))]
    #print(coefMatrix)

    for i in range(len(matrix)):
        coefMatrix[i][matrix[i][0]-1] = 1
        coefMatrix[i][matrix[i][1]-1] = -1
        coefMatrix2[i][matrix[i][0]-1] = 1
        coefMatrix2[i][matrix[i][1]-1] = -1
        coefMatrix2[i][n] = -1 * matrix[i][2]
    
    coef = np.array(coefMatrix)
    coef2 = np.array(coefMatrix2)
    
    return np.linalg.matrix_rank(coef) != np.linalg.matrix_rank(coef2)
    
def DFS(node):
    global point

    parentNode = (node - 1) // 2
    depth = returnDepth(node)

    #print("Node:{}".format(node))
    #print("parentNode:{}".format(parentNode))
    #print("intMatrix[{}]:{}".format(depth-1, intMatrix[depth-1]))
    
    if node > 0:
        tree[node] = copy.copy(tree[parentNode])
        pointList[node] = pointList[parentNode]
        #print("tree[{}]:{}".format(node, tree[node]))
        if node % 2 == 0:
            tree[node].append(intMatrix[depth-1])
            pointList[node] = pointList[node] + intMatrix[depth-1][3]

    #print("tree[{}]:{}".format(node, tree[node]))

    #print(tree[node])
    

    if isContradicting(tree[node]):
        #print("contr")
        return
    elif node >= 2**q - 1:
        #print("pointList[{}]:{}".format(node, pointList[node]))
        if point < pointList[node]:
            point = pointList[node]
        #print(tree[node])
        #print("finish")
    else:
        DFS(2*node+1)
        DFS(2*node+2)
    

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

intMatrix = []
tree = [[]]*(2**(q + 1) - 1)
pointList = [0]*(2**(q + 1) - 1)

point = 0


for i in range(q):
    intMatrix.append(list(map(int, input().split())))

#print(isContradicting([[2, 4, 1, 86568], [1, 4, 0, 90629], [2, 3, 0, 90310], [3, 4, 1, 29211], [1, 2, 0, 94325]]))

#print(2**(q + 1) - 1)

DFS(0)

print(point)

Submission status: Runtime Error

Solution code:
import random

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

intMatrix = []

for i in range(q):
    intMatrix.append(list(map(int, input().split())))

point = 0

seq = [0]*n
seq[0] = 1

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

for i in range(100):
    intMatrixTmp = []
    point_tmp = 0
    for j in range(len(intMatrix)):
        intMatrixTmp.append(intMatrix[j])
        #print(isContradicting(intMatrixTmp))
        if isContradicting(intMatrixTmp) or (bool(random.getrandbits(1)) and j < 3):
            intMatrixTmp.pop()
        else:
            point_tmp += intMatrix[j][3]
    if point < point_tmp:
        point = point_tmp
    
    #print(point_tmp)
    #print(intMatrixTmp)

print(point)

Submission status: Runtime Error

Solution code:
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
a=[]
for i in range(q):
    a.append(list(map(int, input().split())))
 
l = list(range(1,m+1))
big_a = itertools.combinations_with_replacement(l, n)
list_a = list(big_a)
#print(list_a)
s = []
o = []
  
for j in range(len(list_a)):
    nowa = list_a[j]
    z = 0
    while z <= q-1:
        p = a[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: Runtime Error

Solution code:
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ 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: Runtime Error

Solution code:
#166d
x = int(input())
for i in range(-73,73):
    for j in range(-73,73):
        print(i,j)
        if i**5-j**5==x:
            a = i
            b = j
            break
        
print(a,b)

Submission status: Runtime Error

Solution code:
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)


def dfs(nums):

    if len(nums) == N + 1:
        score = 0
        for j in range(Q):
            if nums[B[j]] - nums[A[j]] == C[j]:
                score += D[j]
        return score

    max_score = 0
    for i in range(nums[-1], M+1):
        new_nums = nums + [i]
        max_score = max(max_score, dfs(new_nums))

    return max_score

nums[1]
res = dfs(nums)
print(res)

Submission status: Runtime Error

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

k = []
for _ in range(q):
    k.append(list(map(int, input().split(" "))))

max_score = 0
import itertools
for a in itertools.combinations_with_replacement(range(1, m+1), m):
    score = 0
    for i in range(q):
        if a[k[i][1]-1] - a[k[i][0]-1] == k[i][2]:
            score += k[i][3]
    if score > max_score:
        max_score = score
print(max_score)

Submission status: Runtime Error

Solution code:
import itertools as it

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

ar = [[0]*4]*q

for i in range(q):
    ar[i] = [int(s) for s in input().split()]

A = it.combinations_with_replacement(list(range(1,m+1)),n)
mx = 0

for cnd in A:
    mx_tmp=0
    for i in range(q):
        if(A[ar[i][1]-1] - A[ar[i][0]-1] == ar[i][2]):
            mx_tmp += ar[i][3]
    mx = max(mx,mx_tmp)

print(mx)

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
a=[0]*q
b=[0]*q
c=[0]*q
d=[0]*q
A=[]
for i in range(q):
  a[i],b[i],c[i],d[i]=map(int,input().split())
def score(A):
  sum=0
  for (ai,bi,ci,di) in zip(a,b,c,d):
    if A[ai-1]-A[bi-1]==A[ci-1]:
      sum+=di
  return sum
def fbs(A):
  if len(A)==n:
    return score(A)
  res=0
  for v in range(1,m+1):
    A.append(v)
    res=max(res,fbs(A))
    A.pop()
  return res

print(fbs(A))

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
t=[]
def dfs(s):
  if len(s) == 0:
    t="1"
  else:
    t=s[-1]
  res=[]
  if len(s) == n:
    return [s]
  for i in range(int(t),m+1):
    res+=dfs(s+str(i))
  return res

for i in range(q):
  t.append(list(map(int, input().split())))

ans=0
for i in dfs(""):
  temp=0
  for a,b,c,d in t:
    if int(i[b-1])-int(i[a-1]) == c:
      temp+=d
  ans=max(ans,temp)
print(ans)

Submission status: Runtime Error

Solution code:
    #! /usr/bin/env python3
     
    from fractions import gcd
    from collections import Counter, deque, defaultdict
    from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
    from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
    from itertools import accumulate, product, permutations, combinations
     
    from fractions import gcd
    from collections import Counter, deque, defaultdict
    from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
    from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
    from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
     
    N, M, Q = [int(_) for _ in input().split()]
    abcd = [[int(_) for _ in input().split()] for i in range(Q)]
     
    com = combinations_with_replacement(range(1, M+1), N)
     
    ma = 0
    scores = []
    for i in com:
        score = 0
        for j in abcd:
            if i[j[1]-1] - i[j[0]-1] == j[2]:
                score += j[3]
        if score > ma:
            ma = score
    print(ma)

Submission status: Runtime Error

Solution code:
import itertools
n, m, q = map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]
ans = []
w = list(itertools.combinations(range(1,m+1),n))

for i in w:
    s = 0
    for j in range(q):
        if i[abcd[j][1]-1]-i[abcd[j][0]-1] == abcd[j][2]:
            s += abcd[j][3]
    else:
        ans.append(s)

print(max(ans))

Submission status: Runtime Error

Solution code:
import itertools

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

total = 0

memo = []
number = []
for i in range(m):
    number.append(i+1)
len = m

for j in range((m+3-1)*(m+2-1)*(m)//6):
    memo.append(0)


a = list(itertools.combinations_with_replacement(number,n))
for i in range(q):
    num = list(map(int,input().split()))
    for j in range((m+3-1)*(m+2-1)*(m)//6):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == int(num[2]):
            memo[j] += num[3]
print(max(memo))

Submission status: Runtime Error

Solution code:
import math
n,m,q=map(int,input().split())
abcd=[list(map(int,inpt().split())) for _ in range(q)]
sumlist=[]
for A in math.combinations_with_replacement(range(1,m+1),n)
  sum=0
  for a,b,c,d in abcd:
    if A[b-1]-A[a-1]==c:
      sum+=d
    sumlist.append(sum)
print(max(sumlist))