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 itertools as itr
N,M,Q = map(int,input().split())
sheat = list()
for i in range(Q):
    sheat.append(list(map(int,input().split())))

comb = tuple(itr.combinations(range(1,M+1),N))
Maxsum = 0
print(sheat)
print(comb)
sumd = 0
for i in range(len(comb)):
    ansum = 0
    for j in range(Q):
        if(comb[i][sheat[j][1]-1]-comb[i][sheat[j][0]-1] == sheat[j][2]):
            ansum += sheat[j][3]
           
    if(Maxsum < ansum):
        Maxsum = ansum
    # print(ansum)
print(Maxsum)      
# for i in range(Q):
#     sumd += sheat[i][3]
# print(sumd)
#nCm

#A_1,A_2,A_3,...A_n,M
#A_b-i - A_a-i = C_i  :Sum di

# A= {1,3,4} :comb          ↓sheat
#  i = 1:4 - 1 = 3o 100     [1,3,3]
#      2:3 - 1 = 2o  10     [1,2,2]
#      3:4 - 3 = 1*  10     [2,3,2]
#                   110

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(1, M + 1)]
p = itertools.permutations(l, N)
for p in p:
    total = 0
    for i in range(Q):
        a = m[i][0] - 1
        b = m[i][1] - 1
        A = p[a]
        B = p[b]
        C = B - A
        if m[i][2] == C:
            total = total + m[i][3]
    if res < total:
        res = total
print(res)

Submission status: Wrong Answer

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


def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.combinations(range(1, m+1), 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:
import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [i for i in range(N)]
for A in itertools.product(range(A[0],M+1),repeat=N):
  flag = True
  for n in range(N-1):
    if A[n+1] < A[n]:
      flag = False
      break
  if flag == True:
    for i in range(Q):
      if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
        d_list.append(abcd[i][3])
        
    if sum_d <= sum(d_list):
      sum_d = sum(d_list)
    d_list.clear()
print(sum_d)

Submission status: Wrong Answer

Solution code:
def main():
  n,m,q = map(int,input().split())
  
  a = [1]*n
    
  a_list = []
  while True:
    a_list.append([0, a[:]])
    end = True
    for i in range(n):
      index = n-1-i
      if a[index] < m-i:
        a[index] = a[index] + 1
        for j in range(i):
          a[index+1+j] = a[index]
        end = False
        break
    
    if end:
      break
  
  for _ in range(q):
    tmp = list(map(int, input().split()))
    for a in a_list:
      if a[1][tmp[1]-1] - a[1][tmp[0]-1] == tmp[2]:
        a[0] = a[0] + tmp[3]
  
  max = 0
  for a in a_list:
    if max < a[0]:
      max = a[0]
  
  return max

print(main())

Submission status: Wrong Answer

Solution code:
import heapq

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

for _ in range(Q):
  a,b,c,d = list(map(int, input().split()))
  heapq.heappush(pq, (-d,[a,b,c]))

cnt = [None] * N
res = 0
while pq:
  val, lst = heapq.heappop(pq)
  a,b,c = lst

  if cnt[a-1] and cnt[b-1]:
    if cnt[b-1] - cnt[a-1] == c:
      res += -val
    continue

  if cnt[a-1] is None and cnt[b-1] is None:
    cnt[a-1], cnt[b-1] = 10**5, 10**5+c
  elif cnt[b-1] is None:
    cnt[b-1] = cnt[a-1] + c
  elif cnt[a-1] is None:
    cnt[a-1] = cnt[b-1] - c

  res += -val
print(res)

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
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
    if A[0] == M:
        break
print(ans)

Submission status: Wrong Answer

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

A_list = []
for i in range(10**(N-1),10**N):
    A = [int(x) for x in list(str(i))]
    A_replace = [int(str(a).replace('0', '10')) for a in A]
    if A_replace == sorted(A_replace):
        A_list.append(A_replace)
        
abcd_list = []
for q in range(Q):
    abcd_list.append(list(map(int, input().split())))

for A in A_list:
    tokuten = 0
    for q in range(Q):
        if (A[abcd_list[q][1]-1] - A[abcd_list[q][0]-1] == abcd_list[q][2]):
            tokuten += abcd_list[q][3]

    if tokuten > max_n:
        max_n = tokuten

print(max_n)

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input(). split())
ans = 0
abcd =[]
for _ in range(q):
    abcd.append(list(map(int, input().split())))
for i in range(n**m):
    a = [0] * n
    now = i
    for j in range(n):
        a[-j-1] = now % m
        now = now // m
    ansnow = 0
    for j in range(q):
        if a[abcd[j][1]-1] - a[abcd[j][0]-1] == abcd[j][2]:
            ansnow += abcd[j][3]
    ans = max(ans,ansnow )
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	n,m,q = map(int,input().split())
	qu = [list(map(int,input().split())) for x in range(q)]
	ans = 0
	import itertools

	ans_list = set()
	for i in itertools.combinations_with_replacement([1,2,3,4,5,6,7,8,9,10],n):
		for qul in range(q):
			if i[ qu[qul][1]-1 ] - i[ qu[qul][0]-1 ] == qu[qul][2]:
				ans += qu[qul][3]
		ans_list.add(ans)
		ans = 0
	print(max(ans_list))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N,M,Q = [int(x) for x in input().split()]
#全探索する
from collections import deque
nyu = []
for i in range(Q):
    nyu.append([int(x) for x in input().split()])
d = deque()
a = [0] * (N+1)
e = []
ima = 0
ans = 0
if N == 2:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for i in range(Q):
                aa = nyu[i][0]
                bb = nyu[i][1]
                cc = nyu[i][2]
                dd = nyu[i][3]
                if a[bb] - a[aa] == cc:
                    ima += dd
            ans = max(ans,ima)
            ima = 0
elif N == 3:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for i in range(Q):
                    aa = nyu[i][0]
                    bb = nyu[i][1]
                    cc = nyu[i][2]
                    dd = nyu[i][3]
                    if a[bb] - a[aa] == cc:
                        ima += dd
                ans = max(ans,ima)
                ima = 0

elif N == 4:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for i in range(Q):
                        aa = nyu[i][0]
                        bb = nyu[i][1]
                        cc = nyu[i][2]
                        dd = nyu[i][3]
                        if a[bb] - a[aa] == cc:
                            ima += dd
                    ans = max(ans,ima)
                    ima = 0
elif N == 5:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for i in range(2):
                        sinigami = 2
                    for m in range(l,M+1):
                        a[5] = m
                        for i in range(Q):
                            aa = nyu[i][0]
                            bb = nyu[i][1]
                            cc = nyu[i][2]
                            dd = nyu[i][3]
                            if a[bb] - a[aa] == cc:
                                ima += dd
                        ans = max(ans,ima)
                        ima = 0
elif N == 6:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for i in range(Q):
                                aa = nyu[i][0]
                                bb = nyu[i][1]
                                cc = nyu[i][2]
                                dd = nyu[i][3]
                                if a[bb] - a[aa] == cc:
                                    ima += dd
                            ans = max(ans,ima)
                            ima = 0
elif N == 7:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for i in range(Q):
                                    aa = nyu[i][0]
                                    bb = nyu[i][1]
                                    cc = nyu[i][2]
                                    dd = nyu[i][3]
                                    if a[bb] - a[aa] == cc:
                                        ima += dd
                                ans = max(ans,ima)
                                ima = 0
elif N == 8:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for i in range(Q):
                                        aa = nyu[i][0]
                                        bb = nyu[i][1]
                                        cc = nyu[i][2]
                                        dd = nyu[i][3]
                                        if a[bb] - a[aa] == cc:
                                            ima += dd
                                    ans = max(ans,ima)
                                    ima = 0
elif N == 9:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for r in range(q,M+1):
                                        a[9] = r
                                        for i in range(Q):
                                            aa = nyu[i][0]
                                            bb = nyu[i][1]
                                            cc = nyu[i][2]
                                            dd = nyu[i][3]
                                            if a[bb] - a[aa] == cc:
                                                ima += dd
                                        ans = max(ans,ima)
                                        ima = 0
elif N == 10:
    for z in range(1,M+1):
        a[1] = z
        for i in range(2):
            sinigami = 2
        for j in range(i,M+1):
            a[2] = j
            for k in range(j,M+1):
                a[3] = k
                for l in range(k,M+1):
                    a[4] = l
                    for m in range(l,M+1):
                        a[5] = m
                        for n in range(m,Q+1):
                            a[6] = n
                            for p in range(n,M+1):
                                a[7] = p
                                for q in range(p,M+1):
                                    a[8] = q
                                    for r in range(q,M+1):
                                        a[9] = r
                                        for s in range(r,M+1):
                                            a[10] = s
                                            for i in range(Q):
                                                aa = nyu[i][0]
                                                bb = nyu[i][1]
                                                cc = nyu[i][2]
                                                dd = nyu[i][3]
                                                if a[bb] - a[aa] == cc:
                                                    ima += dd
                                            ans = max(ans,ima)
                                            ima = 0                                                                                  
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
N, M, Q = [int(n) for n in input().split()]
X = [[int(n) for n in input().split()] for _ in range(Q)]
ans = []
for A in combinations_with_replacement(range(1, M+1), N):
    t = 0
    for x in X:
        if A[x[1]-1]-A[x[0]-1] == x[2]:
            t += x[3]
    print(A, t)
    ans.append(t)
print(max(ans))

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]

nums = [i for i in range(1, 10)]
ans = 0
for nums in itertools.combinations_with_replacement(nums, r=n):
	tmp = 0
	for query in queries:
		if nums[query[1] - 1] - nums[query[0] - 1] == query[2]:
			tmp += query[3]
	ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(q)]
ans=0
for v in itertools.permutations(list(range(1,m+1)),n):
    sub=0
    for a in l:
        if v[a[1]-1]-v[a[0]-1]==a[2]:
            sub+=a[3]
    ans=max(ans,sub)
print(ans)

Submission status: Wrong Answer

Solution code:
#input = raw_input

#from copy import deepcopy

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

score_dict = {}

for i in range(1, n):
    for j in range(i+1, n+1):
        key = (i, j)
        score_dict[key] = []

all_inputs = []
for i in range(q):
    a, b, c, d = map(int, input().split(" "))
    key = (a, b)
    score_dict[key].append([c, d])
    all_inputs.append([a, b, c, d])

a_list = [set([]) for i in range(n+1)]
a_list[1] = {0}

all_keys = [(i, cur) for cur in range(n+1) for i in range(1, cur)]
used = {}
for key in all_keys:
    pairs = score_dict[key]
    if len(pairs) == 0:
        used[key] = False

    i, j = key
    assert 1 <= i < j
    ais = a_list[i]
    ajs = a_list[j]
    #ais = deepcopy(a_list[i])
    #ajs = deepcopy(a_list[j])
    for c, d in pairs:
        for ai in ais:
            aj = ai + c
            a_list[j].add(aj)

        for aj in ajs:
            ai = aj - c
            if ai < 0:
                continue
            a_list[i].add(ai)


#print(a_list)

all_a_kumis = []

def f(last, last_i):
    if last_i == n:
        all_a_kumis.append(last)
        return

    cur_i = last_i+1
    if len(a_list[cur_i]) == 0:
        a_list[cur_i] = a_list[cur_i-1]
    for a in a_list[cur_i]:
        if last[-1] <= a:
            cur = last + [a]
            f(cur, cur_i)
        
f([0], 1)
#print(all_a_kumis)

out = 0
for cur_as in all_a_kumis:
    cur = 0
    for a, b, c, d in all_inputs:
        a -= 1
        b -= 1
        if cur_as[b] - cur_as[a] == c:
            cur += d
    out = max(out, cur)

print(out)



#last_end_ki = -1
#queues = []
#all_keys = [(i, cur) for cur in range(n+1) for i in range(1, cur)]
#
#last_end_ki = -1
#ki_dict = {}
#for cur in range(2, n+1):
#    start_ki = last_end_ki+1
#    end_ki = start_ki+cur-2
#    #cur_keys = all_keys[start_ki:end_ki+1]
#    ki_dict[cur] = [start_ki, end_ki]
#    last_end_ki += (cur-1)

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
n = s[0]
m = s[1]
q = s[2]

abcd = []

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

maximum = 0

for i1 in range(1, 11):
    for i2 in range(i1, 11):
        for i3 in range(i2, 11):
            for i4 in range(i3, 11):
                for i5 in range(i4, 11):
                    for i6 in range(i5, 11):
                        for i7 in range(i6, 11):
                            for i8 in range(i7, 11):
                                for i9 in range(i8, 11):
                                    for i10 in range(i9, 11):
                                        iarray = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        goukei = 0
                                        for i in range(q):
                                            if iarray[abcd[i][1] - 1] - iarray[abcd[i][0] - 1] == abcd[i][2]:
                                                goukei = goukei + abcd[i][3]

                                        if goukei > maximum:
                                            maximum = goukei

print(maximum)

Submission status: Wrong Answer

Solution code:
import itertools

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

num_li = itertools.combinations_with_replacement(range(1,m+1),n)

for i in num_li:
    temp = 0
    for j in li:
        a,b,c,d = j
        if i[b-1] - i[a-1] == c:
            temp += d
    ans = max(ans,temp)
    print(temp)
print(ans)

Submission status: Wrong Answer

Solution code:
#n = int(input())
n,m,q = map(int,input().split())
import copy
#a_L = list(map(int,input().split()))
dic = {}

def check(L1):
    h,w = [],[]
    for i in range(len(L1)):
        if L1[i] != 0:
            h.append(L1[i])
    return h == list(sorted(h))

L = [0 for i in range(n)]
L[0] = 1
R = [i for i in range(1,n+1)]
#print(L,R)
x_L = []


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

x_L = sorted(x_L,key=lambda x: x[3],reverse=True)

ans = 0
for i in range(q):
    
    a,b,c,d = x_L[i]
    a = a-1
    b = b-1

    sumi_L = copy.deepcopy(L)

    # 不整合チェック
    if sumi_L[a] == 0:
        sumi_L[a] = R[a]
    
    tmp = sumi_L[a] + c

    if sumi_L[b] == 0 or sumi_L[b] == tmp:
        sumi_L[b] = tmp
    else:
        #print("continu")
        continue
    #print("aaa")
    #tmp_L = list(sorted(sumi_L))
    #print(tmp_L,sumi_L)
    if  check(sumi_L):
        #L[b] = tmp
        L = sumi_L
        ans += d

        
    #a_L = list(map(int,input().split()))
    #dic[d] = [a,b,c,d]  


print(ans)

Submission status: Wrong Answer

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

def check(z):
    y = z.copy()
    y.sort()
    y1 = z.copy()
    while 0 in y:
        y.remove(0)
    while 0 in y1:
        y1.remove(0)
    if y == y1:
        return(1)
    else:
        return(0)

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

serchx = []
for i in x:
    serchx.append(i[0:3])

score = []
for i in x:
    score.append(i[3])

x2 = []
serchx2 = []
for i in x:
    if i[0:3] in serchx2:
        x2[serchx2.index(i[0:3])][3] += i[3]
    else:
        x2.append(i)
        serchx2.append(i[0:3])
        
rx2 = []
for i in x2:
    rx2.append(list(reversed(i)))
rx2.sort(reverse = True)

a = [0]*n

total = 0

for i in rx2:
    if a[i[2]-1]==0 and a[i[3]-1]==0:
        a[i[3]-1] = 1
        a[i[2]-1] = 1 + i[1]
        if check(a) == 1:
            total += i[0]
        else:
            a[i[3]-1] = 0
            a[i[2]-1] = 0
            continue
    elif a[i[2]-1]==0:
        a[i[2]-1] = a[i[3]-1] + i[1]
        if a[i[2]-1]<=m and check(a) == 1:
            total += i[0]
        else:
            a[i[2]-1] = 0
            continue 
    elif a[i[3]-1]==0:
        a[i[3]-1] = a[i[2]-1] - i[1]
        if a[i[3]-1]>=1 and check(a) == 1:
            total += i[0]
        else:
            a[i[3]-1] = 0
            continue 
    else:
        if a[i[2]-1] - a[i[3]-1] == i[1]:
            total += i[0]
        continue
print(total)

Submission status: Wrong Answer

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

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


soutai_a = [inf for i in range(n)]
for i in range(q):
    info[i][0] -= 1
    info[i][1] -= 1


info.sort(key = lambda x: x[3], reverse = True)
soutai_a[info[0][0]] = 0
score = 0
for i in range(q):
    if soutai_a[info[i][1]] != inf and soutai_a[info[i][0]] != inf:
        if info[i][1] - info[i][0] == info[i][2]:
            score += info[i][3]
    else:
        if soutai_a[info[i][1]] == inf:
            soutai_a[info[i][1]] = soutai_a[info[i][0]] + info[i][2]
        elif soutai_a[info[i][0]] == inf:
            soutai_a[info[i][0]] = soutai_a[info[i][1]] - info[i][2]
        score += info[i][3]

print(score)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
N, M, Q = LI()

abcd = []
for i in range(Q):
    a, b, c, d = LI()
    a -= 1
    b -= 1
    abcd.append([a, b, c, d])
ans = 0
if Q <= 2:
    for q in range(Q):
        ans += abcd[q][-1]
    print(ans)
    sys.exit()

def cal_ans(A):
    ans = 0
    for i in range(Q):
        a, b, c, d = abcd[i]
        if A[b] - A[a] == c:
            ans += d
    return ans

def n2kdigit(n, k):
    bi=''
    before = 1
    while n!=0:
        if before <= (n % k):
            # print(n)
            bi+=str(n%abs(k))
            before = n % k
            if k<0:n=-(-n//k)
            else:n=n//k
        else:
            return None
    if len(bi[::-1]) < N:
        return None
    return bi
ans = 0
for i in range(M ** (N)):
    A = n2kdigit(i, M)
    if A is not None:
        ans = max(ans, cal_ans([int(i) for i in A]))
ans = max(ans, cal_ans([0 for i in range(N)]))
print(ans)

Submission status: 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())
    a -= 1
    b -= 1
    query.append([a,b,c,d])

query.sort(key= lambda x: x[1])

num = '1' * n
rows = [num]

for a,b,c,d in query:
    for row in rows:
        if int(row[b]) - int(row[a]) == c:
            continue
        else:
            row = list(row)
            row[b] = str(int(row[a]) + c)
            row = ''.join(row)
            rows.append(row)

rows = set(rows)

max_ans = 0
for row in rows:
    ans = 0
    row = list(row)
    for a,b,c,d in query:
        if int(row[b]) - int(row[a]) == c:
            ans += d
    if ans > max_ans:
        max_ans = ans

print(max_ans)

Submission status: Wrong Answer

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)
ans=0
M=[0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  M[i]=1
cursor=n
breakflag=0
while True:
  ev=0
  for i in range(q):
    if M[b[i]-1]-M[a[i]-1]==c[i]:
      ev+=d[i]
  if ev>ans:
    ans=ev
  while True:
    if M[cursor-1]<m:
      M[cursor-1]+=1
      for i in range(cursor,n):
        M[i]=M[cursor-1]
      break
    cursor-=1
    if cursor==0:
      breakflag=1
      break
  if breakflag==1:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
arg = list(map(int, input().split())) # 1行, 配列
N = arg[0]
M = arg[1]
Q = arg[2]

listA=[]
maxim = 0

while True:
  try:
    listA.append(list(map(int,input().split())))
  except:
    break;
A = []
As = []

for x in range(1,M+1):
  A = [x] * N
  As.append(list(A))
  for i in list(range(N-1,0,-1)):
    while A[i] < M:
      A[i] = A[i] + 1
      As.append(list(A))

for item in As:
  letMaxim = 0
  for l in listA:
    if item[l[1]-1] - item[l[0]-1] == l[2]:
      letMaxim = letMaxim + l[3]
  if maxim < letMaxim:
    maxim = letMaxim

print(maxim)

Submission status: Wrong Answer

Solution code:
li = list(map(int, input().split()))
lists = []
for a in range(li[2]):
    lists.append(list(map(int, input().split())))
listA = []
for i in range(1, li[0] + 1):
    if i > li[1]:
        listA.append(li[1])
    else:
        listA.append(i)
totals = []
for i in range(li[2]):
    ai = lists[i][0]-1
    bi = lists[i][1]-1
    ci = lists[i][2]
    di = lists[i][3]
    total = 0
    if not listA[bi] - listA[ai] == ci:
        listA[bi] = listA[ai] + ci
    for j in range(li[2]):
        if listA[lists[j][1]-1] - listA[lists[j][0]-1] == lists[j][2]:
            total = total + lists[j][3]   
    totals.append(total)
print(max(totals))

Submission status: Wrong Answer

Solution code:
import itertools
n, m, q = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]

nums = [i for i in range(10)]
ans = 0
for nums in itertools.combinations_with_replacement(nums, r=n):
	tmp = 0
	for query in queries:
		if nums[query[1] - 1] - nums[query[0] - 1] == query[2]:
			tmp += query[3]
	ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for _ in range(Q):
  ai,bi,ci,di=map(int,input().split())
  a.append(ai)
  b.append(bi)
  c.append(ci)
  d.append(di)
A=0
ans=0
def nshin(n, base):
  if (int(n/base)):
    return nshin(int(n/base), base) + str(n%base)
  return str(n%base)
for i in range(1,M**N):
  A+=i
  Ai=nshin(A,M).zfill(N)
  gokei=0
  for j in range(Q):
    if int(Ai[b[j]-1])+1-int(Ai[a[j]-1])+1==c[j]:
      gokei+=d[j]
  ans=max(ans,gokei)
print(ans)

Submission status: Wrong Answer

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

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

while(s[0] != m):

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

    ans1[t] = ans
    t += 1
    ans = 0

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

        num = n-1

    print(s)




print(max(ans1))

Submission status: Wrong Answer

Solution code:
import itertools

N, M, Q = map(int, input().split())
x1 = [0]*Q
x2 = [0]*Q
x3 = [0]*Q
x4 = [0]*Q

for i in range(Q):
    x1[i], x2[i], x3[i], x4[i] = map(int, input().split())

score = 0
tmp = 0
lis = range(1, M+1)
A = []

for i in itertools.combinations(lis, N):
    A.append(list(i))

for i in range(len(A)):
    for j in range(Q):
        if(A[i][x2[j]-1] - A[i][x1[j]-1] == x3[j]): tmp += x4[j]
    if(tmp>score): score = tmp
    tmp = 0

print(score)