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: Wrong Answer

Solution code:
#!/usr/bin/python3
import math
import copy


def minx(idx, cl, m):
    mi = 1
    for i in range(idx):
        mi = max(mi, cl[idx])
    return mi

def maxx(idx, cl, m):
    ma = m
    for i in range(idx + 1, len(cl)):
        if cl[i] > 0 and cl[i] < ma:
            ma = cl[i]
    return ma

def maxp(qs, idx, cl, n, m, cache):
    k = str(idx) + ':' + ':'.join(map(str, cl))
    if k in cache:
        return cache[k]

    (a, b, c, d) = qs[idx]

    if idx == len(qs) - 1:
        mp = 0
        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    mp = d
                    break
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)
                if mia <= na <= maa:
                    mp = d
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                

                if mib <= nb <= mab:
                    mp = d

        elif cl[b - 1] - cl[a - 1] == c:
            mp = d

        cache[k] = mp
    else:
        #not select
        mp = maxp(qs, idx + 1, cl, n, m, cache)

        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)                
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        else:
            if cl[b - 1] - cl[a - 1] == c:
                mp = max(mp, d + maxp(qs, idx + 1, cl, n, m, cache))
                
        cache[k] = mp

    return cache[k]

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

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

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 0, l, n, m, cache))

Submission status: Wrong Answer

Solution code:


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

# dp[i][j] : i番目まで使い、1<=...<=a_n=jの範囲での(最適値, [a_i-a_1, ..., 0])
dp = [[None] * m for _ in range(n)] # n * m
for j in range(m):
    dp[0][j] = (0, [(0,)])
for i in range(1,n):
#     print(i)
    for j in range(m):
        dpij = 0
        ind = 0
        best_tup = []
        for jj in range(j+1):
            val, tups = dp[i-1][jj]
            for tup in tups:
                tmp_val = val
                for a,b,c in abc2d:
                    if b==i and c==(tup[a]+(j-jj)):
                        tmp_val += abc2d[a,b,c]
                if tmp_val > dpij:
                    ind = jj
                    dpij = tmp_val
                    best_tup = [tup]
                elif tmp_val==dpij:
                    best_tup.append(tup)
        for ii,tup in enumerate(best_tup):
            best_tup[ii] = tuple(item+(j-ind) for item in tup) + (0,)
        dp[i][j] = (dpij, best_tup)
#         print(dp[i][j])
print(max(dp[n-1][j][0] for j in range(m)))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, m, q = na()
abcd = nan(q)

def dfs(s):
    if len(s) == n + 1:
        res = 0
        for i in range(q):
            a, b, c, d = abcd[i]
            if s[b] - s[a] == c:
                res += d
        return res
    res = 0
    for i in range(s[-1], m + 1):
        news = s[:]
        news.append(i)
        res = max(res, dfs(news))
    return res

print(dfs([0]))

Submission status: Wrong Answer

Solution code:
import itertools

N,M,Q = map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(0,Q,1):
    tmp = list(map(int,input().split()))
    a.append(tmp[0])
    b.append(tmp[1])
    c.append(tmp[2])
    d.append(tmp[3])

max_score = -1
for i in itertools.combinations_with_replacement(range(1,M,1),N):
    score = 0
    for j in range(0,Q,1):
        if i[b[j]-1]-i[a[j]-1]==c[j]:
            score += d[j]
    if max_score < score:
        max_score = score

print(max_score)

Submission status: Wrong Answer

Solution code:
import copy

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

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


A_list =[-1] * N
sum_max = 0

A_list_list =[]

def dfs(curr, count):
    if count >= N:
        sum_ = 0
        
        for q in range(Q):
            ai = abcd_list[q][0]
            bi = abcd_list[q][1]
            ci = abcd_list[q][2]
            di = abcd_list[q][3]

            if A_list[bi - 1] - A_list[ai - 1] == ci:
                sum_ += di
        global sum_max
        if sum_max <= sum_:
            sum_max = sum_

        A_list_list.append(copy.copy(A_list))

        return

    l = N - count + 1
    # 次の値を求める
    for i in range(curr, M - l + 3):
        A_list[count] = i
        dfs(i, count + 1)

dfs(1, 0)
print(sum_max)

Submission status: Wrong Answer

Solution code:
import copy

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

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


A_list =[-1] * N
sum_max = 0

A_list_list =[]

def dfs(curr, count):
    if count >= N:
        sum_ = 0
        
        for q in range(Q):
            ai = abcd_list[q][0]
            bi = abcd_list[q][1]
            ci = abcd_list[q][2]
            di = abcd_list[q][3]

            if A_list[bi - 1] - A_list[ai - 1] == ci:
                sum_ += di
        global sum_max
        if sum_max <= sum_:
            sum_max = sum_

        A_list_list.append(copy.copy(A_list))

        return

    l = N - count + 1
    # 次の値を求める
    for i in range(curr, M - l + 3):
        A_list[count] = i
        dfs(i, count + 1)

dfs(0, 0)
print(sum_max)

# 未完

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement as cmb

n,m,q=map(int,input().split())
abcd=[]
for i in range(q):
    ll=map(int,input().split())
    ll=[ww-1 for ww in ll]
    abcd.append(ll)
ans=0
for li in cmb(range(1,m+1),n):
    kari=0
    for i in abcd:
        if li[i[1]]-li[i[0]]==i[2]+1:
            kari+=i[3]+1
    print(li,kari)
    ans=max(ans,kari)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

# dp[i][j] : i番目まで使い、1<=...<=a_n=jの範囲での(最適値, [a_i-a_1, ..., 0])
dp = [[None] * m for _ in range(n)] # n * m
for j in range(m):
    dp[0][j] = (0, (0,))
for i in range(1,n):
    for j in range(m):
        dpij = 0
        ind = 0
        for jj in range(j+1):
            val, tup = dp[i-1][jj]
            for a,b,c in abc2d:
                if b==i and c==(tup[a]+(j-jj)):
                    val += abc2d[a,b,c]
            if val > dpij:
                ind = jj
                dpij = val
        dp[i][j] = (dpij, tuple(item+(j-ind) for item in dp[i-1][ind][1])+(0,))
print(max(dp[n-1][j][0] for j in range(m)))

Submission status: Wrong Answer

Solution code:


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

# dp[i][j] : i番目まで使い、1<=...<=a_n=jの範囲での(最適値, [a_i-a_1, ..., 0])
dp = [[None] * m for _ in range(n)] # n * m
for j in range(m):
    dp[0][j] = (0, (0,))
for i in range(1,n):
    for j in range(m):
        dpij = 0
        ind = 0
        for jj in range(j+1):
            val, tup = dp[i-1][jj]
            for a,b,c in abc2d:
                if b==i and c==(tup[a]+(j-jj)):
                    val += abc2d[a,b,c]
            if val > dpij:
                ind = jj
                dpij = val
        dp[i][j] = (dpij, tuple(item+(j-ind) for item in dp[i-1][ind][1])+(0,))
print(max(dp[n-1][j][0] for j in range(m)))

Submission status: Wrong Answer

Solution code:
import itertools
N, M, Q = map(int, input().split())
m = list()
res = -100
for i in range(Q):
    n = list(map(int, input().split()))
    m.append(n)
l = [x for x in range(M + 1)]
p = itertools.combinations_with_replacement(l, N)
for p in p:
    total = 0
    for i in range(Q):
        num = 0
        a = m[i][0]
        b = m[i][1]
        A = p[a - 1]
        B = p[b - 1]
        C = B - A
        if m[i][2] == C:
            num = num + m[i][3]
            total = total + num
    if res < total:
        res = total
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import math
import copy


def minx(idx, cl, m):
    mi = 1
    for i in range(idx):
        mi = max(mi, cl[idx])
    return mi

def maxx(idx, cl, m):
    ma = m
    for i in range(idx + 1, len(cl)):
        if cl[i] > 0 and cl[i] < ma:
            ma = cl[i]
    return ma

def maxp(qs, idx, cl, n, m, cache):
    k = str(idx) + ':' + ':'.join(map(str, cl))
    if k in cache:
        return cache[k]

    (a, b, c, d) = qs[idx]

    if idx == len(qs) - 1:
        mp = 0
        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = d
                    break
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = d
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                

                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = d

        elif cl[b - 1] - cl[a - 1] == c:
            mp = d

        cache[k] = mp
    else:
        #not select
        mp = maxp(qs, idx + 1, cl, n, m, cache)

        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = minx(a - 1, cl, m)
            maa = maxx(a - 1, cl, m)

            mib = minx(b - 1, cl, m)
            mab = maxx(b - 1, cl, m)
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = minx(a - 1, cl, m)
                maa = maxx(a - 1, cl, m)                
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = minx(b - 1, cl, m)
                mab = maxx(b - 1, cl, m)                
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        else:
            if l[b - 1] - l[a - 1] == c:
                mp = max(mp, d + maxp(qs, idx + 1, cl, n, m, cache))
                
        cache[k] = mp

    return cache[k]

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

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

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 0, l, n, m, cache))

Submission status: Wrong Answer

Solution code:
ans = 0

def search_all(length, mnam):
    ans = 0
    l = [0] * length
    for _ in range(mnam ** length):
        for i in range(-1,-length,-1):
            if(l[i]>=mnam):
                l[i] = 0
                l[i - 1] += 1
        # print(l)
        l[-1] += 1
        s = 0
        for a, b, c, d in qx:
            s += d if (l[b-1] - l[a-1] == c) else 0
        ans = max(ans, s)
    return  ans


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

print(search_all(n,m))


#print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations as cmb

n,m,q=map(int,input().split())
abcd=[]
for i in range(q):
    ll=map(int,input().split())
    ll=[ww-1 for ww in ll]
    abcd.append(list(ll))

ans=0
for li in cmb(range(m),n):
    kari=0
    for i in abcd:
        if li[i[1]]-li[i[0]]==i[2]+1:
            kari+=i[3]+1
    ans=max(ans,kari)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import math
import copy

def maxp(qs, idx, cl, n, m, cache):
    k = str(idx) + ':' + ':'.join(map(str, cl))
    if k in cache:
        return cache[k]

    (a, b, c, d) = qs[idx]

    if idx == len(qs) - 1:
        mp = 0
        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = max(cl[:a - 1])
            maa = max(cl[a:] + [ m ])

            mib = max(cl[:b - 1])
            mab = max(cl[b:] + [ m ])
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = d
                    break
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = max(cl[:a - 1])
                maa = max(cl[a:] + [ m ])
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = d
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = max(cl[:b - 1])
                mab = max(cl[b:] + [ m ])
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = d

        elif cl[b - 1] - cl[a - 1] == c:
            mp = d

        cache[k] = mp
    else:
        #not select
        mp = maxp(qs, idx + 1, cl, n, m, cache)

        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = max(cl[:a - 1])
            maa = max(cl[a:] + [ m ])

            mib = max(cl[:b - 1])
            mab = max(cl[b:] + [ m ])
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = max(cl[:a - 1])
                maa = max(cl[a:] + [ m ])
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = max(cl[:b - 1])
                mab = max(cl[b:] + [ m ])
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        else:
            if l[b - 1] - l[a - 1] == c:
                mp = max(mp, d + maxp(qs, idx + 1, cl, n, m, cache))
                
        cache[k] = mp

    return cache[k]

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

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

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 0, l, n, m, cache))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import math
import copy

def maxp(qs, idx, cl, n, m, cache):
    k = str(idx) + ':' + ':'.join(map(str, cl))
    if k in cache:
        return cache[k]

    (a, b, c, d) = qs[idx]

    if idx == len(qs) - 1:
        if cl[a - 1] == 0 or cl[b - 1] == 0:
            cache[k] = d
        elif cl[b - 1] - cl[a - 1] == c:
            cache[k] = d            
        else:
            cache[k] = 0
    else:
        mp = 0
        #not select
        mp = maxp(qs, idx + 1, cl, n, m, cache)

        if cl[a - 1] == 0 and cl[b - 1] == 0:
            mia = max(cl[:a - 1])
            maa = max(cl[a:] + [ m ])

            mib = max(cl[:b - 1])
            mab = max(cl[b:] + [ m ])
            
            for i in range(mia, maa + 1):
                if mib <= i + c <= mab:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = i
                    ncl[b - 1] = i + c
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[a - 1] == 0:
            na = cl[b - 1] - c
            if na > 0:
                mia = max(cl[:a - 1])
                maa = max(cl[a:] + [ m ])
                if mia <= na <= maa:
                    ncl = copy.copy(cl)
                    ncl[a - 1] = na
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        elif cl[b - 1] == 0:
            nb = cl[a - 1] + c
            if nb <= m:
                mib = max(cl[:b - 1])
                mab = max(cl[b:] + [ m ])
                if mib <= nb <= mab:
                    ncl = copy.copy(cl)                    
                    ncl[b - 1] = nb
                    mp = max(mp, d + maxp(qs, idx + 1, ncl, n, m, cache))
                    
        else:
            if l[b - 1] - l[a - 1] == c:
                mp = max(mp, d + maxp(qs, idx + 1, cl, n, m, cache))
                
        cache[k] = mp

    return cache[k]

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

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

qs.sort()
         
l = [ 0 for i in range(n) ]
l[0] = 1
cache = {}

print(maxp(qs, 0, l, n, m, cache))

Submission status: Wrong Answer

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

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


def calcPoint(num):
    ret = 0
    for q in range(Q):
        if num[query[q][1] - 1] - num[query[q][0] - 1] == query[q][2]:
            ret += query[q][3]

    return ret


ans = 0


def dfs(suu, keta):
    global ans
    if keta == N:
        ans = max(ans, calcPoint(suu))
        print(*suu)
        return

    co = suu.copy()

    for i in range(suu[keta - 1], M):
        co[keta] = i
        dfs(co, keta + 1)


retsu = [0] * N

dfs(retsu, 1)
print(ans)

Submission status: Wrong Answer

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

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


def calcPoint(num):
    ret = 0
    for q in range(Q):
        if num[query[q][1] - 1] - num[query[q][0] - 1] == query[q][2]:
            ret += query[q][3]

    return ret


ans = 0


def dfs(suu, keta):
    global ans
    if keta == N:
        ans = max(ans, calcPoint(suu))
        return

    co = suu.copy()

    for i in range(suu[keta - 1], M + 1):
        co[keta] = i
        dfs(co, keta + 1)


retsu = [0] * N

dfs(retsu, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n,m,q=map(int,input().split())
List = [[int(j) for j in input().split()] for i in range(q)]
total = 0
d = 0
lis = list(range(1,m+1))

for pair in itertools.combinations(lis, n):
    for i in range(q):
        if pair[List[i][1]-1] - pair[List[i][0]-1] == List[i][2]:
            total += List[i][3]
    if d <= total:
        d = total
        print(d)
    total = 0

print(d)

Submission status: Wrong Answer

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

l=[]
for n in range(Q):
    l.append(list(map(int,input().strip().split())))
             
def judge(x,l):
    dsum=0
    for e in l:
        if x[e[1]]-x[e[0]]==e[2]:
            dsum+=e[3]
    return dsum

ans=0
for a in range(M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    for j in range(i,M+1):
                                        balls=[0,a,b,c,d,e,f,g,h,i,j]
                                        temp=judge(balls,l)
                                        if temp>=ans:
                                            ans=temp

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for i in range(Q)]
ans = 0
for x in combinations_with_replacement(range(1, 11), 10):
    tmp = 0

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


print(ans)

Submission status: Wrong Answer

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

l=[]
for n in range(Q):
    l.append(list(map(int,input().strip().split())))
             
def judge(x,l):
    dsum=0
    for e in l:
        if balls[e[1]]-balls[e[0]]==e[2]:
            dsum+=e[3]
    return dsum

ans=0
for a in range(M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    for j in range(i,M+1):
                                        balls=[0,a,b,c,d,e,f,g,h,i,j]
                                        temp=judge(balls,l)
                                        if temp>=ans:
                                            ans=temp

print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score_ret = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score_ret += d
        return score_ret
    
    else:
        for nu in range(min_lim, m+1):
            new_nums = nums + [nu]
            score = dfs(new_nums, length+1, nu)
            ans = max(ans, score)
    return ans

n,m,q = map(int,input().split())
req = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([-1], 0, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(A):
  global ans
  if len(A)==N: 
    now=0
    for i in l:
      if A[i[1]-1]-A[i[0]-1]==i[2]:
        now+=i[3]
    ans=max(ans,now)
    return A


  A.append(A[-1])
  while A[-1]<=M:
    dfs(A)
    A[-1]+=1
    
    
  



N,M,Q=[int(x) for x in input().rstrip().split()]
A=[1]
l=[]
ans=0
for i in range(Q):
  abcd=[int(x) for x in input().rstrip().split()]
  l.append(abcd)
dfs(A)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for _ 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(19, m+1):
                                        tmp = 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 += d
                                        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, Q = map(int, input().split(" "))
que = deque()
for i in range(1, M + 1):
    que.append([i])

while True:
    now = que.popleft()
    if len(now) == N:
        que.append(now)
        break

    last = now[-1] if len(now) > 0 else 1
    for i in range(last, M + 1):
        que.append(now + [i])

print(que)
cond = []
for _ in range(Q):
    cond.append(tuple(map(int, input().split(" "))))

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

Submission status: Wrong Answer

Solution code:
comb = []
def f(n,cnt,ls):
    if cnt == n:
        comb.append(ls)
        return
    for i in range(ls[cnt-1],11):
        tmp = ls.copy()
        tmp[cnt] = i
        f(n,cnt+1,tmp)
    return
ma = lambda :map(int,input().split())
ni = lambda:int(input())

n,m,q = ma()
abcd = []
for i in range(q):
    abcd.append(list(ma()))
ls = [1]*(n+1)
f(n,0,ls)
ans = 0
for A in  comb:
    tmp = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] ==c:
            tmp +=d
    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, Q = map(int, input().split(" "))
que = deque()
que.append([])

while True:
    now = que.popleft()
    if len(now) == N:
        break

    last = now[-1] if len(now) > 0 else 1
    for i in range(last, M + 1):
        que.append(now + [i])

cond = []
for _ in range(Q):
    cond.append(tuple(map(int, input().split(" "))))

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

Submission status: Wrong Answer

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

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

ans = 0
N = [i+1 for i in range(m)]
for v in product(N,repeat = n):
    num = 0
    for i in range(q):
        if v[b[i]] - v[a[i]] == c[i]:
            num += d[i]
    ans = max(ans,num)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
lis=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    lis.append((a,b,c,d))
    
from itertools import combinations_with_replacement

co=list(combinations_with_replacement(range(1,11),10))

ans=0
for status in co:
    tmp_score=0
    for a,b,c,d in lis:
        if status[b-1]-status[a-1]==c:
            tmp_score+=d
    ans=max(ans,tmp_score)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

ans = -1
def dfs(l):
  global ans
  if len(l) == n:
    ans = max(check(l),ans)
  else:
    if len(l) == 0:
      mx = 1
    else:
      mx = l[-1]
    for i in range(mx,11):
      tmpl = l + [i]
      dfs(tmpl)

def check(l):
  res = 0
  for a,b,c,d in abcd:
    a -= 1
    b -= 1
    if l[b]-l[a] == c:
      res += d
  return res

dfs([])
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
L = []
for i in range(Q):
  L.append(list(map(int, input().split())))
  #print(L[i][1])
import itertools

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

v=list(itertools.combinations(l,N))
print(v)
for j in range(len(v)):
  for i in range(Q):
    if (v[j][L[i][1]-1] - v[j][L[i][0]-1])==L[i][2]:
      print(v[j][L[i][1]-1],v[j][L[i][0]-1],L[i][2])
      ans+=L[i][3]
print(ans)

'''

for i in range(Q):   
  for v in itertools.combinations(l,N):
    if (v[L[i][1]-1] - v[L[i][0]-1])==L[i][2]:
      print(v[L[i][1]-1],v[L[i][0]-1],L[i][2])
      ans+=L[i][3]
print(ans)
'''