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:
import sys
import math
from collections import Counter
import itertools
import fractions
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
 
N,M,Q=MI()
a=LLI(Q)
x=[0]*M
for i in range(1,M+1):
    x[i-1]=i
A=itertools.combinations_with_replacement(x,N)

ma=0
for z in A:
    su = 0
    for c in a:
        if z[1] > N or z[0] > N:
            break
        if z[c[1]-1] - z[c[0]-1] == c[2]:
            su += c[3]
    ma=max(ma,su)
print(ma)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
S=[0]*Q;t=0;d=0;A=[0]*10
for i in range(Q):
  a,b,c,d=map(int,input().split())
  S[i]=[a,b,c,d]
#print(S)
for i1 in range(M):
  for i2 in range(M):
    for i3 in range(M):
      for i4 in range(M):
        for i5 in range(M):
          for i6 in range(M):
            for i7 in range(M):
              for i8 in range(M):
                for i9 in range(M):
                  for i10 in range(M):
                    A=[i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for i in range(Q):
                      if A[S[i][1]-1]-A[S[i][0]-1]==S[i][2]:
                        d=d+S[i][3]
                    t=max(t,d)
                    d=0
print(t)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(aa):
        if len(aa)==n+1:
            res=0
            for a,b,c,d in ad:
                if aa[b]-aa[a]==c:res+=d
            return res

        res=-1
        for a in range(aa[-1],m+1):
            res=max(dfs(aa+[a]),res)
        return res

    n,m,q=MI()
    ad=LLI(q)
    print(dfs([0]))

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

dabc = []
for a,b,c,d in abcd:
    dabc.append([d,a,b,c])
dabc.sort(reverse=True)

dp = [float("inf")] * 100

ans = 0
for d, a, b, c in dabc:
    if dp[a] == float("inf") or dp[b] == float("inf"):
        if c < dp[a] and c < dp[b]:
            dp[a] = min(c, dp[a])
            dp[b] = min(c, dp[b])
            ans += d

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


import numpy as np
import itertools

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

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


#s = [[0]*4]*Q
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q

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

max_point = 0
    
for i in range(0,len(A)):
    point = 0
    for j in range (0,Q):
        if A[i][b[j]-1]-A[i][a[j]-1] == c[j]:
            point += d[j]
    max_point = max(point,max_point)
    
#
#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
        
print(max_point)

Submission status: Wrong Answer

Solution code:
import itertools
s=list(map(int,input().split()))
t=[list(map(int,input().split())) for i in range(s[2])]
li=[x for x in range(1,s[0]+1)]
lity=list(itertools.combinations_with_replacement(li,s[0]))
ans=0
for k in lity:
  vmax=0
  for l in t:
    if k[l[1]-1]-k[l[0]-1]==l[2]:
      vmax+=l[3]
  ans=max(ans,vmax)
print(ans)

Submission status: Wrong Answer

Solution code:
def next(a):
    a = a.copy()
    a[0] -= 1
    if a[0] == -1:
        if a == [-1]:
            return [0]
        a = next(a[1:])
        a.insert(0, a[0])
    return a

n, m, q = (int(j) for j in input().split())
l = []
for i in range(1, q + 1):
    a, b, c, d = (int(j) for j in input().split())
    l.append((a, b, c, d))

a = [m] * n
j = 0
while a != [0] * n:
    k = 0
    for i in l:
        if a[i[1] - 1] - a[i[0] - 1] == i[2]:
            k += i[3]
    if k > j:
        j = k
    a = next(a)
print(j)

Submission status: Wrong Answer

Solution code:
import math

a, b, n = map(int, input().split())
x = min(n, b-1)
print(math.floor(a*x/b)-a*math.floor(x/b))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(i=0):
        if i==n:
            res=0
            for a,b,c,d in ad:
                if aa[b-1]-aa[a-1]==c:res+=d
            return res

        res=-1
        for a in range(aa[i-1],m+1):
            aa[i]=a
            res=max(dfs(i+1),res)
        return res

    n,m,q=MI()
    ad=LLI(q)
    aa=[0]*n
    print(dfs())

main()

Submission status: Wrong Answer

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

ans = 0

for i in range(2**Q):
    s = bin(i)
    p = [P[j] for j in range(len(s) - 2) if int(s[2 + j]) == 1]
    min_s = [[0] * N for _ in range(N)]
    max_s = [[M - 1] * N for _ in range(N)]
    flg = True
    for i in range(0, len(p)):
        a = p[i][0]
        b = p[i][1]
        c = p[i][2]
        a -= 1
        b -= 1
        if c >= min_s[a][b] and c <= max_s[a][b]:
            for j in range(a, b + 1):
                min_s[a][j] = max(min_s[a][j], p[i][2])
            for j in range(b, N):
                max_s[a][j] = min(min_s[a][j], p[i][2])
        else:
            flg = False
    if flg:
        ans = max(ans, sum([p[k][3] for k in range(len(p))]))
print(ans)

Submission status: Wrong Answer

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

def calculate(A):
    total = 0
    for abcdi in abcd:
        a = abcdi[0] - 1
        b = abcdi[1] - 1
        c = abcdi[2]
        d = abcdi[3]
        if A[b] - A[a] == c:
            total += d
    # print(A, total)

    return total

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

print(maximum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.product(range(1, m+1), repeat=n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

import numpy as np
arrays = list(np.array_split(aa, q))

solve(n, m, q, arrays)

Submission status: Wrong Answer

Solution code:
N,M,Q = list(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())
A = [1] * 11
ans = 0
anstmp = 0

for ai in range(1,11):
    A[0] = ai
    for bi in range(ai,11):
        A[1] = bi
        for ci in range(bi,11):
            A[2] = ci
            for di in range(ci,11):
                A[3] = di
                for ei in range(di,11):
                    A[4] = ei
                    for fi in range(ei,11):
                        A[5] = fi
                        for gi in range(fi,11):
                            A[6] = gi
                            for hi in range(gi,11):
                                A[7] = hi
                                for ii in range(hi,11):
                                    A[8] = ii
                                    for ji in range(ii,11):
                                        A[9] = ji
                                        for ki in range(ji,11):
                                            A[10] = ki

            for i in range(Q):
                if A[b[i]-1] - A[a[i]-1] == c[i]:
                    anstmp += d[i]
            if anstmp >= ans :
                ans = anstmp
            anstmp = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q=map(int,input().split())
qs = [list(map(int,input().split())) for i in range(q)]
mids = [i for i in range(m)]
max_ans= 0
for mid in itertools.combinations_with_replacement(mids, n-1):
    if sum(mid)>m-1:
        continue
    sum_ans=0
    for i in qs:
        sum_mid = 0
        for j in range(i[0]-1,i[1]-1):
            sum_mid += mid[j]
        if sum_mid == i[2]:
            sum_ans += i[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)

Submission status: Wrong Answer

Solution code:
import math

a,b,n = map(int, input().split())
tmp = int(n/b)
result = 0
if tmp != 0:
    result = b - 1
else:
    result = n
print(math.floor((a*result)/b) - a*math.floor(result/b))

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
a=[0 for i in range(Q)]
b=[0 for i in range(Q)]
c=[0 for i in range(Q)]
d=[0 for i in range(Q)]
A=[0 for i in range(N)]
def swap(a,b,c):
    kari=a[b]
    a[b]=a[c]
    a[c]=kari
    return a
for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int, input().split())
for i in range(0,N):
    max=d[0]
    if(N==1):
        break
        for j in range(1,N-i):
            if d[j]>max:
                max=d[j]
                d=swap(d,j,j-1)
                a=swap(a,j,j-1)
                b=swap(b,j,j-1)
                c=swap(c,j,j-1)
sum=0
recode={}
for i in range(0,Q):
    if a[i] in recode.keys() and b[i] in recode.keys():
        continue
    else:
        recode[a[i]]=1
        recode[b[i]]=1
        sum+=d[i]
print(sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

N, M, Q = map(int , input().split(" "))
A = np.array([[int(n) for n in input().split(" ")]])
for d in range(Q-1):
  b = [int(n) for n in input().split(" ")]
  A = np.vstack([A, b])
nolist = list(range(1, M+1))
dsum = 0
for v in itertools.combinations(nolist, N):
  d = 0
  vnew = sorted(v)
  for i in range(A.shape[0]):
    intli = A[i]
    if vnew[intli[1]-1] - vnew[intli[0]-1] == intli[2]:
      d += intli[3]
    else:
      pass
  if d > dsum:
    dsum = d
print(dsum)

Submission status: Wrong Answer

Solution code:
import sys
N,M,Q=map(int,input().split())
ABC=[]
ans=0
take=set([])
for i in range(Q):
  ABC+=[list(map(int,input().split()))]
ABC.sort(key=lambda x: x[3],reverse=True)
for i in range(Q):
  if len(take)==N:
    print(ans)
    sys.exit()
  ans+=ABC[i][3]
  take.add(ABC[i][0])
  take.add(ABC[i][1])
  take=set(take)
print(ans)

Submission status: Wrong Answer

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

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):
    Table = np.random.randint(1,m+1, (n, 1))
    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.88:
        print(max(Sum_cor))
        break

Submission status: Wrong Answer

Solution code:
import itertools

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

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

A = list(range(1, M + 1))
ans_max = 0
for AA in itertools.combinations(A, N):
    ans = 0
    for ll in L:
        a = ll[0]
        b = ll[1]
        c = ll[2]
        d = ll[3]
        Ab = AA[b-1]
        Aa = AA[a-1]
        s = Ab - Aa
        if (s == c):
            ans += d
    if (ans_max < ans):
        ans_max = ans
print(ans_max)

Submission status: Wrong Answer

Solution code:
n,m,q = list(map(int,input().split()))
a = [[]]*q
for i in range(q):
    a[i] = list(map(int,input().split()))
ans = 0
def calc(x):
    cnt = 0
    for j in range(q):
        if x[a[j][1]-1] - x[a[j][0]-1] == a[j][2]:
            cnt += a[j][3]
    return cnt
l = [0]*n
for k in range(10*n):
    b = str(k).zfill(n)
    for o in range(n):
        if o == 0:
            l[o] = 1
        else:
            l[o] = int(b[o])
            if l[o] < l[o-1]:
                break        
    if ans < calc(l):
        ans = calc(l)
print(ans)

Submission status: Wrong Answer

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

# a,b,c,d = map(int, lQ[i].split())

high_score = 0

A = [1]*N

while True:
    for i in reversed(range(1,N)):
        if A[i] < M:
            A[i] +=1
            break
    score = 0
    
    for j in range(Q):
        a,b,c,d = map(int, lQ[j].split())
        if A[b-1]-A[a-1]==c:
            score += d
    
    if score > high_score:
        high_score = score
        
    if A[1] == M:
        break;         


print(high_score)

Submission status: Wrong Answer

Solution code:

import math

def ls_incr(arg_ls, max_n):
	rv_ls = arg_ls[::-1]
	for i,n in enumerate(rv_ls):
		if n >= max_n: continue
		rv_ls[i] += 1
		return rv_ls[::-1]
	return False

# input
inp_ls = input().split(" ")
n,m,q = [int(e) for e in inp_ls[:3]]

nums_ls = []
for i in range(q):
	one_inp_ls = input().split(" ")
	a,b,c,d = [int(e) for e in one_inp_ls[:4]]
	nums_ls.append([a,b,c,d])

# calc
a_ls = [1 for i in range(n)]	# init
max_sum = 0
while True:
	sum_val = 0
	for a,b,c,d in nums_ls:
		if c == (a_ls[b-1]-a_ls[a-1]):
			sum_val += d
	# 最大値更新
	if max_sum < sum_val: max_sum = sum_val
	# incr
	a_ls = ls_incr(a_ls, m)
	if a_ls is False: break

# reult
print(max_sum)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(Q)]
A = [1] * N
ans = 0

for a, b, c, d in l:
    if A[b-1] - A[a-1] == c:
        ans += d
if M > 1:
    while True:
        A[-1] += 1
        ans_ = 0
        for a, b, c, d in l:
            if A[b-1] - A[a-1] == c:
                ans_ += d
        if ans_ > ans:
            ans = ans_

        if A[-1] == M + 1:
            for i in range(1, N):
                A[-(i+1)] += 1
                for k in range(N-(i+1), N):
                    A[k] = A[-(i+1)]
                if A[-(i+1)] != M + 1:
                    break
        print(A)
        if A[0] == M:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m, q = [int(x) for x in input().split()]
 
tmp = []
for i in range(q):
    a, b, c, d = [int(x) for x in input().split()]
    tmp.append([a, b, c, d])

t = list(itertools.combinations_with_replacement(range(1, m + 1), m))

score = 0
for _t in t:
    _s = 0
    for a, b, c, d in tmp:
        try:
            if c == _t[b - 1] - _t[a - 1]:
                _s += d
        except:
            pass
    score = max(_s, score)
print(score)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int, input().split())
a,b,c,d = [],[],[],[]
for i in range(Q):
  ai,bi,ci,di = map(int, input().split())
  a += [ai]
  b += [bi]
  c += [ci]
  d += [di]

Aint = int('1'*N)
Mint = int('{}'.format(M)*N)
A = [1]*N
ans = 0

for _ in range(100):
  #print(Aint)
  dsum = 0
  for i in range(Q):
    ai,bi,ci,di = a[i], b[i], c[i], d[i]
    if A[bi-1]-A[ai-1] == ci:
      dsum += di
  ans = max(ans, dsum)

  #終了条件
  if Aint==Mint:
    break

  #終了しない場合は次の数字
  for j in range(1,N+1):
    if A[N-j]==M:
      continue
    else:
      A[N-j] += 1
      break
  for k in range(1, j):
    A[N-k] = A[N-j]
  Aint=int(''.join(map(str, A)))

print(ans)

Submission status: Wrong Answer

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(100):
        rem = np.random.randint(1,m+1)
        if rem in Table:
            Table.remove(rem)
            c-=1
            if c <=n:
                return Table
    return make_table(n, m)



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.88:
        print(max(Sum_cor))
        break

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a = []
b = []
c = []
d = []
for i in range(q):
    _a, _b, _c, _d = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

#print(n, m, q, a, b, c, d)
def get_score(A, a, b, c, d, q):
    s = 0
    for i in range(q):
        b_i = b[i]
        a_i = a[i]
        c_i = c[i]
        if A[b_i - 1]- A[a_i - 1]==c_i:
            s += d[i]
    return s

result = -1
import itertools
for A in itertools.combinations(list(range(1, m + 1)), n):
    score = get_score(A, a, b, c, d, q)

    #print(A, score)
    if score > result:
        result = score

print(result)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q=map(int,input().split())
abcd=[None]*q
for i in range(q):
    abcd[i]=list(map(int,input().split()))
num=0
for l in list(map(list, itertools.combinations(sorted(list(range(1,m+1))*m), n))):
    num_ = 0
    for x in abcd:
        if l[x[1]-1]-l[x[0]-1] == x[2]:
            num_ += x[3]
    num = max(num ,num_)
print(num)

Submission status: Wrong Answer

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

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

A = [1 for i in range(N)]
ans = [0]
wa = 0
for i in range(N):
  for j in range(M):
    A[N - i - 1] = 1 + j
    for k in range(Q):
      if A[x[k][1] - 1] - A[x[k][0] - 1] == x[k][2]:
        wa += x[k][3]
    ans.append(wa)
    wa = 0
    
ans.sort(reverse=True)
print(ans[0])

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
cnt = 0
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())
for j in range(m-n+1):
    if b[j] - a[j] + (m-n) == c[j]:
        cnt += d[j]
print(cnt)

Submission status: Wrong Answer

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

def solve(pas, max):
    a = [None]*n
    a[0] = 1

    cnt = 0

    if a[x[pas][0]-1] == None:
        a[x[pas][0]-1] = x[pas][0]-1

    if a[x[pas][1]-1] == None:
        a[x[pas][1]-1] = a[x[pas][0]-1] + x[pas][2]

    for i in range(q):
        if a[x[i][0]-1] == None:
            a[x[i][0]-1] = x[i][0]-1

        if a[x[i][1]-1] == None:
            a[x[i][1]-1] = a[x[i][0]-1] + x[i][2]

        #print(a[x[i][1]-1], a[x[i][0]-1] ,"== ",x[i][2], " :" , x[i][3])
        #print(a[x[i][1]-1] - a[x[i][0]-1] == x[i][2])
        if a[x[i][1]-1] - a[x[i][0]-1] == x[i][2]:
            cnt += x[i][3]

    #print(cnt)

    if max < cnt:
        max = cnt
    return max

max = 0
for i in range(q):
    max = solve(i, max)
print(max)

Submission status: Wrong Answer

Solution code:
n,m,q = list(map(int,input().split()))
a = [[]]*q
for i in range(q):
    a[i] = list(map(int,input().split()))
ans = 0
def calc(x):
    cnt = 0
    for j in range(q):
        if x[a[j][1]-1] - x[a[j][0]-1] == a[j][2]:
            cnt += a[j][3]
    return cnt
l = [0]*n
for k in range(10*n):
    b = str(k).zfill(n)
    for o in range(n):
        l[o] = int(b[o])
    if ans < calc(l):
        ans = calc(l)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time



def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

def rec(li, i, M, N, a, b, c, d, cans):
    # print(i, li, len(li), N)
    if len(li) >= N:
        # print(li, N)
        ans = 0
        for j in range(len(a)):
            if li[b[j]-1] - li[a[j]-1] == c[j]:
                ans += d[j]
        # print(ans, li)
        return ans

    # for j in range(1, len(lis[i])):
    #     for v in lis[i][j]:

    ans = 0
    if len(cans[i]) == 0:
        ans = max(ans, rec(li + [1], i+1, M, N, a, b, c, d, cans))
    else:
        for v in cans[i]:
            ans = max(ans, rec(li + [v], i+1, M, N, a, b, c, d, cans))

    return ans


def main():
    N, M, Q = MI()
    a = [0] * Q
    b = [0] * Q
    c = [0] * Q
    d = [0] * Q
    didx = [None] * Q
    lis = [[[] for i in range(N+1)] for i in range(N+1)]
    cans = [set() for i in range(N+1)]

    for i in range(Q):
        a[i], b[i], c[i], d[i] = MI()
        # didx[i] = (d[i], i)

    # cans = []
    # for i in range(1, M+1):
    #     cans += [i] * N

    # for li in combinations(cans, N):
    #     print(li)

    # didx.sort(reverse=True)

    for i in range(Q):
        # lis[b[i]][a[i]].append(c[i])
        lis[a[i]][b[i]].append(c[i])

    cans[min(a)].add(1)

    for i in range(1, N+1):
        # print(i, lis[i])
        for j in range(len(lis[i])):
            for k in lis[i][j]:
                for v in cans[i]:
                    # print(v, k)
                    if v + k <= M:
                        cans[j].add(v + k)
    # print(cans)
    # print(didx)
    print(rec([], 1, M, N, a, b, c, d, cans))
    # print(sum(d))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a = []
b = []
c = []
d = []
for i in range(q):
    _a, _b, _c, _d = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

print(n, m, q, a, b, c, d)
def get_score(A, a, b, c, d, q):
    s = 0
    for i in range(q):
        b_i = b[i]
        a_i = a[i]
        c_i = c[i]
        if A[b_i - 1]- A[a_i - 1]==c_i:
            s += d[i]
    return s

result = -1
import itertools
for A in itertools.combinations(list(range(1, m + 1)), n):
    score = get_score(A, a, b, c, d, q)

    #print(A, score)
    if score > result:
        result = score

print(result)

Submission status: Wrong Answer

Solution code:
a,b,n=map(int,input().split())
x = int(a*n/b)-a*int(n/b)
bdash = n // b * b - 1

y = int(a*bdash/b)-a*int(bdash/b)

if a < n and b<n:
    print(max(min(a - 1, b - 1), y, x))
else:
    print(max(y,x))

Submission status: Wrong Answer

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

l = []

def inc(ary):
  s = ''
  ary[-1] += 1
  for i in range(len(ary)-1, -1, -1):
    v = ary[i]
    if v > (m - (n-1) + i):
      if i == 0:
        return False
      ary[i-1] += 1
      ary[i] = i+1
  return ary

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

a_tmp = [num for num in range(1, n+1)]
# print(n, m, q)
# print(l)
# print(a_tmp)

ans = 0
l_len = len(l)
while True:
  ans_tmp = 0
  for i in range(l_len):
    a, b, c, d = l[i]
    if (a_tmp[b] - a_tmp[a]) == c:
      ans_tmp += d
  if ans_tmp > ans:
    ans = ans_tmp
  
  # a_tmp のインクリメント
  a_tmp = inc(a_tmp)
  if a_tmp == False:
    break
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, q = list(map(int, input().split()))
a = []
b = []
c = []
d = []
for i in range(q):
    _a, _b, _c, _d = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

print(n, m, q, a, b, c, d)
def get_score(A, a, b, c, d, q):
    s = 0
    for i in range(q):
        b_i = b[i]
        a_i = a[i]
        c_i = c[i]
        if A[b_i - 1]- A[a_i - 1]==c_i:
            s += d[i]
    return s

result = -1
import itertools
for A in itertools.combinations(list(range(1, m + 1)), n):
    score = get_score(A, a, b, c, d, q)
    print(A, score)
    if score > result:
        result = score

print(result)