Problem:


Score : 800 points

Problem Statement

There is a grid with R rows and C columns.
We call the cell in the r-th row and c-th column (r，c).

Mr. Takahashi wrote non-negative integers into N of the cells, that is, he wrote a non-negative integer a_i into (r_i，c_i) for each i (1≤i≤N).
After that he fell asleep.

Mr. Aoki found the grid and tries to surprise Mr. Takahashi by writing integers into all remaining cells.
The grid must meet the following conditions to really surprise Mr. Takahashi.

Condition 1: Each cell contains a non-negative integer.

Condition 2: For any 2×2 square formed by cells on the grid, the sum of the top left and bottom right integers must always equal to the sum of the top right and bottom left integers.

Determine whether it is possible to meet those conditions by properly writing integers into all remaining cells.

Constraints

2≤R，C≤10^5

1≤N≤10^5

1≤r_i≤R

1≤c_i≤C

(r_i，c_i) ≠ (r_j，c_j) (i≠j)

a_i is an integer.

0≤a_i≤10^9

Input

The input is given from Standard Input in the following format:

R C
N
r_1 c_1 a_1
r_2 c_2 a_2
:
r_N c_N a_N

Output

Print Yes if it is possible to meet the conditions by properly writing integers into all remaining cells.
Otherwise, print No.

Sample Input 1

2 2
3
1 1 0
1 2 10
2 1 20

Sample Output 1

Yes

You can write integers as follows.

Sample Input 2

2 3
5
1 1 0
1 2 10
1 3 20
2 1 30
2 3 40

Sample Output 2

No

There are two 2×2 squares on the grid, formed by the following cells:

Cells (1，1), (1，2), (2，1) and (2，2)

Cells (1，2), (1，3), (2，2) and (2，3)

You have to write 40 into the empty cell to meet the condition on the left square, but then it does not satisfy the condition on the right square.

Sample Input 3

2 2
3
1 1 20
1 2 10
2 1 0

Sample Output 3

No

You have to write -10 into the empty cell to meet condition 2, but then it does not satisfy condition 1.

Sample Input 4

3 3
4
1 1 0
1 3 10
3 1 10
3 3 20

Sample Output 4

Yes

You can write integers as follows.

Sample Input 5

2 2
4
1 1 0
1 2 10
2 1 30
2 2 20

Sample Output 5

No

All cells already contain a integer and condition 2 is not satisfied.



Sample input:
2 2
3
1 1 0
1 2 10
2 1 20


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
r, c = [int(k) for k in input().split()]
m = [[-1 for x in range(c)] for y in range(r)]

n = int(input())
for i in range(n):
	x, y, z = [int(k) for k in input().split()]
	m[x - 1][y - 1] = z

def eval(mr, mc):
	co = sum(x.count(-1) for x in m)

	if (co == 0):
		if (m[mr][mc] + m[mr + 1][mc + 1] == m[mr][mc + 1] + m[mr + 1][mc]):
			return True
		else:
			return False

	if (co == 4):
		m[mr][mc] = 0
		m[mr + 1][mc + 1] = 0
		m[mr][mc + 1] = 0
		m[mr + 1][mc] = 0
		return True 

	if (co == 1):
		if (m[mr][mc] == -1):
			cc = m[mr][mc + 1] + m[mr + 1][mc] - m[mr + 1][mc + 1]
			if (cc < 0):
				return False
			else:
				m[mr][mc] = cc
				return True

		if (m[mr][mc + 1] == -1):
			cc = m[mr][mc] + m[mr + 1][mc + 1] - m[mr + 1][mc]
			if (cc < 0):
				return False
			else:
				m[mr][mc + 1] = cc
				return True

		if (m[mr + 1][mc] == -1):
			cc = m[mr][mc] + m[mr + 1][mc + 1] - m[mr][mc + 1]
			if (cc < 0):
				return False
			else:
				m[mr + 1][mc] = cc
				return True

		if (m[mr + 1][mc + 1] == -1):
			cc = m[mr][mc + 1] + m[mr + 1][mc] - m[mr][mc]
			if (cc < 0):
				return False
			else:
				m[mr + 1][mc + 1] = cc
				return True

	if (co == 2):
		if (m[mr][mc] == -1):
			m[mr][mc] = m[mr][mc + 1] if (m[mr][mc + 1] != -1) else m[mr + 1][mc] 
			return eval(mr, mc)

		if (m[mr][mc + 1] == -1):
			m[mr][mc + 1] = m[mr][mc] if (m[mr][mc] != -1) else m[mr + 1][mc + 1] 
			return eval(mr, mc)

		if (m[mr + 1][mc] == -1):
			m[mr + 1][mc] = m[mr][mc] if (m[mr][mc] != -1) else m[mr + 1][mc + 1] 
			return eval(mr, mc)

		if (m[mr + 1][mc + 1] == -1):
			m[mr + 1][mc + 1] = m[mr][mc + 1] if (m[mr][mc + 1] != -1) else m[mr + 1][mc] 
			return eval(mr, mc)

	if (co == 3):
		ml = m[mr][mc] + m[mr + 1][mc + 1] + m[mr][mc + 1] + m[mr + 1][mc] + 3
		m[mr][mc] = ml
		m[mr + 1][mc + 1] = ml
		m[mr][mc + 1] = ml
		m[mr + 1][mc] = ml
		return True 

mre = "Yes"

for i in range(r - 1):
	for j in range(c - 1):
		if (eval(i, j) == False):
			mre = "No"
			break

	if (mre == "No"):
		break

print (mre)

Submission status: Time Limit Exceeded

Solution code:
str_in1 = input().split()

size = []
for c in str_in1:
    size.append(int(c))

size.append(int(input()))

g = []
for i in range(0, size[0]):
    g.append([-1]*size[1])
    
for i in range(0, size[2]):
    str_in = input().split()

    coord = []
    for c in str_in:
        coord.append(int(c))

    g[coord[0]-1][coord[1]-1] = coord[2]

res = True

while res:
    old_g = []
    for k in g:
        old_g.append(list(k))
    
    for x in range(0, size[0] - 1):
        if not res:
            break
        for y in range(0, size[1] - 1):
            if not res:
                break
            a = 0
            b = 0
            c = 0
            d = 0
            if g[x][y] == -1:
                a = -1
            if g[x+1][y] == -1:
                b = -1
            if g[x][y+1] == -1:
                c = -1
            if g[x+1][y+1] == -1:
                d = -1

            if a+b+c+d == -1:
                if a == -1:
                    g[x][y] = g[x+1][y] + g[x][y+1] - g[x+1][y+1]
                elif b == -1:
                    g[x+1][y] = g[x][y] + g[x+1][y+1] - g[x][y+1]
                elif c == -1:
                    g[x][y+1] = g[x][y] + g[x+1][y+1] - g[x+1][y]
                elif d == -1:
                    g[x+1][y+1] = g[x+1][y] + g[x][y+1] - g[x][y]
                if g[x][y] < 0 or g[x+1][y] < 0 or g[x][y+1] < 0 or g[x+1][y+1] < 0:
                    res = False
                    break
                continue

            if a+b+c+d == 0:
                if not g[x][y] + g[x+1][y+1] == g[x+1][y] + g[x][y+1]:
                    res = False
                    break
    if not res:
        break
                    
    for k in range(0, len(old_g)):
        for i in range(0,len(old_g[k])):
            if not old_g[k][i] == g[k][i]:
                continue
    break

if res:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
r, c = [int(k) for k in input().split()]
m = [[-1 for x in range(c)] for y in range(r)]

n = int(input())
for i in range(n):
	x, y, z = [int(k) for k in input().split()]
	m[x - 1][y - 1] = z

def eval(mr, mc):
	co = sum(x.count(-1) for x in m)

	if (co == 0):
		if (m[mr][mc] + m[mr + 1][mc + 1] == m[mr][mc + 1] + m[mr + 1][mc]):
			return True
		else:
			return False

	if (co == 4):
		m[mr][mc] = 0
		m[mr + 1][mc + 1] = 0
		m[mr][mc + 1] = 0
		m[mr + 1][mc] = 0
		return True 

	if (co == 1):
		if (m[mr][mc] == -1):
			cc = m[mr][mc + 1] + m[mr + 1][mc] - m[mr + 1][mc + 1]
			if (cc < 0):
				return False
			else:
				m[mr][mc] = cc
				return True

		if (m[mr][mc + 1] == -1):
			cc = m[mr][mc] + m[mr + 1][mc + 1] - m[mr + 1][mc]
			if (cc < 0):
				return False
			else:
				m[mr][mc + 1] = cc
				return True

		if (m[mr + 1][mc] == -1):
			cc = m[mr][mc] + m[mr + 1][mc + 1] - m[mr][mc + 1]
			if (cc < 0):
				return False
			else:
				m[mr + 1][mc] = cc
				return True

		if (m[mr + 1][mc + 1] == -1):
			cc = m[mr][mc + 1] + m[mr + 1][mc] - m[mr][mc]
			if (cc < 0):
				return False
			else:
				m[mr + 1][mc + 1] = cc
				return True

	if (co == 2):
		if (m[mr][mc] == -1):
			m[mr][mc] = m[mr][mc + 1] if (m[mr][mc + 1] != -1) else m[mr + 1][mc] 
			return eval(mr, mc)

		if (m[mr][mc + 1] == -1):
			m[mr][mc + 1] = m[mr][mc] if (m[mr][mc] != -1) else m[mr + 1][mc + 1] 
			return eval(mr, mc)

		if (m[mr + 1][mc] == -1):
			m[mr + 1][mc] = m[mr][mc] if (m[mr][mc] != -1) else m[mr + 1][mc + 1] 
			return eval(mr, mc)

		if (m[mr + 1][mc + 1] == -1):
			m[mr + 1][mc + 1] = m[mr][mc + 1] if (m[mr][mc + 1] != -1) else m[mr + 1][mc] 
			return eval(mr, mc)

	if (co == 3):
		ml = m[mr][mc] + m[mr + 1][mc + 1] + m[mr][mc + 1] + m[mr + 1][mc] + 3
		m[mr][mc] = ml
		m[mr + 1][mc + 1] = ml
		m[mr][mc + 1] = ml
		m[mr + 1][mc] = ml
		return True 

mre = "Yes"

for i in range(r - 1):
	for j in range(c - 1):
		if (eval(i, j) == False):
			mre = "No"

print (mre)

Submission status: Time Limit Exceeded

Solution code:
str_in1 = input().split()

size = []
for c in str_in1:
    size.append(int(c))

size.append(int(input()))

g = []
for i in range(0, size[0]):
    g.append([-1]*size[1])
    
for i in range(0, size[2]):
    str_in = input().split()

    coord = []
    for c in str_in:
        coord.append(int(c))

    g[coord[0]-1][coord[1]-1] = coord[2]

res = True

while res:
    old_g = []
    for k in g:
        old_g.append(list(k))
    
    for x in range(0, size[0] - 1):
        for y in range(0, size[1] - 1):
            a = 0
            b = 0
            c = 0
            d = 0
            if g[x][y] == -1:
                a = -1
            if g[x+1][y] == -1:
                b = -1
            if g[x][y+1] == -1:
                c = -1
            if g[x+1][y+1] == -1:
                d = -1

            if a+b+c+d == -1:
                if a == -1:
                    g[x][y] = g[x+1][y] + g[x][y+1] - g[x+1][y+1]
                elif b == -1:
                    g[x+1][y] = g[x][y] + g[x+1][y+1] - g[x][y+1]
                elif c == -1:
                    g[x][y+1] = g[x][y] + g[x+1][y+1] - g[x+1][y]
                elif d == -1:
                    g[x+1][y+1] = g[x+1][y] + g[x][y+1] - g[x][y]
                if g[x][y] < 0 or g[x+1][y] < 0 or g[x][y+1] < 0 or g[x+1][y+1] < 0:
                    res = False
                continue

            if a+b+c+d == 0:
                if not g[x][y] + g[x+1][y+1] == g[x+1][y] + g[x][y+1]:
                    res = False
                    break
                    
    for k in range(0, len(old_g)):
        for i in range(0,len(old_g[k])):
            if not old_g[k][i] == g[k][i]:
                continue
    break

if res:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def check_squares(grid, coord, isFilled):
    rows, cols = len(grid), len(grid[0])
    r, c = coord[0], coord[1]
    sums = []

    if r - 1 >= 0 and c - 1 >= 0: # check upper left square
        if isFilled and (grid[r][c - 1] + grid[r - 1][c] != grid[r][c] + grid[r - 1][c - 1]):
            raise ValueError('not filled correctly')

        if grid[r][c - 1] is not None and grid[r - 1][c] is not None and grid[r - 1][c - 1] is not None:
            sums.append((grid[r][c - 1] + grid[r - 1][c]) - grid[r - 1][c - 1])

    if r - 1 >= 0 and c + 1 < cols: # check upper right square
        if isFilled and (grid[r - 1][c] + grid[r][c + 1] != grid[r][c] + grid[r - 1][c + 1]):
            raise ValueError('not filled correctly')

        if grid[r - 1][c] is not None and grid[r - 1][c + 1] is not None and grid[r][c + 1] is not None:
            sums.append((grid[r - 1][c] + grid[r][c + 1]) - grid[r - 1][c + 1])

    if r + 1 < rows and c - 1 >= 0: # check lower left
        if isFilled and (grid[r][c] + grid[r + 1][c - 1] != grid[r][c - 1] + grid[r + 1][c]):
            raise ValueError('not filled correctly')

        if grid[r][c - 1] is not None and grid[r + 1][c] is not None and grid[r + 1][c - 1] is not None:
            sums.append((grid[r][c - 1] + grid[r + 1][c]) - grid[r + 1][c - 1])

    if r + 1 < rows and c + 1 < cols: # check lower right
        if isFilled and (grid[r + 1][c + 1] + grid[r][c] != grid[r][c + 1] + grid[r + 1][c]):
            raise ValueError('not filled correctly')

        if grid[r][c + 1] is not None and grid[r + 1][c] is not None and grid[r + 1][c + 1] is not None:
            sums.append((grid[r + 1][c] + grid[r][c + 1]) - grid[r + 1][c + 1])

    if len(sums) > 1 and len(set(sums)) > 1:
        raise ValueError('Square cannot be filled in')
    elif len(sums) == 1:
        if sums[0] < 0:
            raise ValueError('Value would have to be negative')
        return sums[0]
    else:
        return None

r, c = map(int, raw_input().split())
n = int(raw_input())
grid = [ [None for i in range(c)] for j in range(r) ]

for i in range(n):
    line = map(int, raw_input().split())
    grid[line[0] - 1][line[1] - 1] = line[2]

possible = True
filled = (n == r * c)

for i in range(r):
    for j in range(c):
        if grid[i][j] is None or filled:
            try:
                result = check_squares(grid, (i, j), filled)
                grid[i][j] = result
            except ValueError:
                print 'No'
                exit()

print 'Yes'

Submission status: Time Limit Exceeded

Solution code:
#read in input
r, c = map(int, raw_input().split())
n = int(raw_input())

RC = [[-1]*c for _ in range(r)]

for _ in range(n):
  ri, ci, ai = map(int, raw_input().split())
  RC[ri-1][ci-1] = ai


def numNeg(nums):
  return sum(map((lambda x: 1 if x < 0 else 0), nums))

def negIndex(nums):
  for i in range(len(nums)):
    if nums[i] < 0:
      return i

flag = True
wrong = False
while(flag):
  flag = False
  for ri in range(r - 1):
    for ci in range(c - 1):
      nums = [0] * 4
      nums[0] = RC[ri][ci]
      nums[1] = RC[ri][ci+1]
      nums[2] = RC[ri+1][ci]
      nums[3] = RC[ri+1][ci+1]
      if(numNeg(nums) == 0):
        if nums[0] + nums[3] != nums[1] + nums[2]:
          wrong = True
          break
      elif(numNeg(nums) == 1):
        flag = True
        i = negIndex(nums)
        if(i == 0):
          RC[ri][ci] = nums[1] + nums[2] - nums[3]
          if(RC[ri][ci] < 0):
            wrong = True
            break
        elif(i == 1):
          RC[ri][ci+1] = nums[0] + nums[3] - nums[2]
          if(RC[ri][ci+1] < 0):
            wrong = True
            break
        elif(i == 2):
          RC[ri+1][ci] = nums[0] + nums[3] - nums[1]
          if(RC[ri+1][ci] < 0):
            wrong = True
            break
        elif(i == 3):
          RC[ri+1][ci+1] = nums[1] + nums[2] - nums[0]
          if(RC[ri+1][ci+1] < 0):
            wrong = True
            break
    if wrong:
      break
  if wrong:
    break

for ri in range(r - 1):
  x = -1
  y = -1
  for ci in range(c):
    a = RC[ri][ci]
    b = RC[ri+1][ci]
    if a == -1 or b == -1:
      continue
    elif x == -1:
      x = a
      y = b
    elif a - b != x - y:
      wrong = True
      break
  if wrong:
    break

for ci in range(c - 1):
  x = -1
  y = -1
  for ri in range(r):
    a = RC[ri][ci]
    b = RC[ri][ci+1]
    if a == -1 or b == -1:
      continue
    elif x == -1:
      x = a
      y = b
    elif a - b != x - y:
      wrong = True
      break
  if wrong:
    break


if wrong:
  print "No"
else:
  print "Yes"

Submission status: Time Limit Exceeded

Solution code:
[R,C]=[int(x) for x  in raw_input().split()]
N=int(raw_input())
A=[[-1 for i in range(C+2)] for j in range(R+2)]
Qlist=[]
Nlist=[]
for i in range(N):
    [r,c,a]=[int(x) for x  in raw_input().split()]
    A[r][c]=a
    Qlist.append([r,c,a])
Qlist.sort(key=lambda x:x[1])
Qlist.sort(key=lambda x:x[0])
ans=1
while(1):
    for i in range(N):
        [r,c,a]=Qlist[i]
        if A[r+1][c+1]!=-1:
            if A[r+1][c]!=-1 and A[r][c+1]==-1:
                A[r][c+1]=max(0,a+A[r+1][c+1]-A[r+1][c])
                Nlist.append([r,c+1,A[r][c+1]])
            elif A[r+1][c]==-1 and A[r][c+1]!=-1:
                A[r+1][c]=max(0,a+A[r+1][c+1]-A[r][c+1])
                Nlist.append([r+1,c,A[r+1][c]])
            elif A[r+1][c]!=-1 and A[r][c+1]!=-1:
                if A[r+1][c]+A[r][c+1]!=a+A[r+1][c+1]:
                    ans=0
                    break
        if A[r+1][c-1]!=-1:
            if A[r+1][c]!=-1 and A[r][c-1]==-1:
                A[r][c-1]=max(0,a+A[r+1][c-1]-A[r+1][c])
                Nlist.append([r,c-1,A[r][c-1]])
            elif A[r+1][c]==-1 and A[r][c-1]!=-1:
                A[r+1][c]=max(0,a+A[r+1][c-1]-A[r][c-1])
                Nlist.append([r+1,c,A[r+1][c]])
            elif A[r+1][c]!=-1 and A[r][c-1]!=-1:
                if A[r+1][c]+A[r][c-1]!=a+A[r+1][c-1]:
                    ans=0
                    break
        if A[r-1][c+1]!=-1:
            if A[r-1][c]!=-1 and A[r][c+1]==-1:
                A[r][c+1]=max(0,a+A[r-1][c+1]-A[r-1][c])
                Nlist.append([r,c+1,A[r][c+1]])
            elif A[r-1][c]==-1 and A[r][c+1]!=-1:
                A[r-1][c]=max(0,a+A[r-1][c+1]-A[r][c+1])
                Nlist.append([r-1,c,A[r-1][c]])
            elif A[r-1][c]!=-1 and A[r][c+1]!=-1:
                if A[r-1][c]+A[r][c+1]!=a+A[r-1][c+1]:
                    ans=0
                    break
        if A[r-1][c-1]!=-1:
            if A[r-1][c]!=-1 and A[r][c-1]==-1:
                A[r][c-1]=max(0,a+A[r-1][c-1]-A[r-1][c])
                Nlist.append([r,c-1,A[r][c-1]])
            elif A[r-1][c]==-1 and A[r][c-1]!=-1:
                A[r-1][c]=max(0,a+A[r-1][c-1]-A[r][c-1])
                Nlist.append([r-1,c,A[r-1][c]])
            elif A[r-1][c]!=-1 and A[r][c-1]!=-1:
                if A[r-1][c]+A[r][c-1]!=a+A[r-1][c-1]:
                    ans=0
                    break
    else:
        break
    Qlist=Nlist[:]
    Nlist=[]
    N=len(Qlist)
    if N==0:
        break
if ans:
    print 'Yes'
else:
    print 'No'

Submission status: Time Limit Exceeded

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

import numpy as np

li = []

r, c = map(int, raw_input().split())
n = input()
mat = -np.ones((r, c))
for i in range(n):
    rn, cn, an = map(int, raw_input().split())
    mat[rn - 1, cn - 1] = an
    li.append([rn, cn, an])

for i in range(r):
    if i > 0:
        diffs = [mat[i, k] - mat[i - 1, k] for k in range(c)]
        diff = max(diffs) if (mat[i] > 0).any() else 0
        # print "diff", i, diff
    for j in range(c):
        if i > 0:
            mat[i, j] = mat[i - 1, j] + diff
        else:
            mat[i, j] = j if mat[i, j] < 0 else mat[i, j]

# print mat

isfalsified = False
for i in range(n):
    rn, cn, an = li[i]
    if mat[rn - 1, cn - 1] != an:
        isfalsified = True

if (mat < 0).any():
    print "No"
elif isfalsified:
    print "No"
else:
    print "Yes"

Submission status: Memory Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(R, C) = reads()
N = read()

d = defaultdict(list)
V = set()

for _ in range(N):
  (r, c, a) = reads()
  (r, c) = (r-1, c-1)
  d["R", r].append((("C", c), a))
  d["C", c].append((("R", r), a))
  V.add(("R", r))
  V.add(("C", c))

def walk(v):
  V.discard(v)
  for (w, a) in d[v]:
    wcol = a - col[v]
    if w in col:
      if col[w] != wcol:
        print("No"); exit()
    else:
      col[w] = wcol
      walk(w)

while len(V) > 0:
  v = V.pop()
  col = dict()
  col[v] = 0
  walk(v)
  rcol = min(a for (v, a) in col.items() if v[0] == "R")
  ccol = min(a for (v, a) in col.items() if v[0] == "C")
  if rcol + ccol < 0:
    print("No"); exit()

print("Yes")

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp is not VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) is not 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] is "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] is "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")

Submission status: Memory Limit Exceeded

Solution code:
## this submission is just for checking pypy3 performance
## the code is borrowed from http://code-festival-2016-quala.contest.atcoder.jp/submissions/899133


from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
setrecursionlimit(1000000)
 
(R, C) = reads()
N = read()
 
d = defaultdict(list)
V = set()
 
for _ in range(N):
  (r, c, a) = reads()
  (r, c) = (r-1, c-1)
  d["R", r].append((("C", c), a))
  d["C", c].append((("R", r), a))
  V.add(("R", r))
  V.add(("C", c))
 
def walk(v):
  V.discard(v)
  for (w, a) in d[v]:
    wcol = a - col[v]
    if w in col:
      if col[w] != wcol:
        print("No"); exit()
    else:
      col[w] = wcol
      walk(w)
 
while len(V) > 0:
  v = V.pop()
  col = dict()
  col[v] = 0
  walk(v)
  rcol = min(a for (v, a) in col.items() if v[0] == "R")
  ccol = min(a for (v, a) in col.items() if v[0] == "C")
  if rcol + ccol < 0:
    print("No"); exit()
 
print("Yes")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**15] * h
dw = defaultdict(list)
for i in range(n):
    r,c,a = map(int, input().split())
    r -= 1
    c -= 1
    mind[r] = min(mind[r], a)
    dw[c].append((a,r))
# 0未満になる要素があるか判定
es = [[] for _ in range(h)]
def main():
    ans = True
    for c in range(w):
        if len(dw[c])<=1:
            continue
        dw[c].sort()
        tmp = 0
        for i in range(len(dw[c])-1):
            u = dw[c][i][1]
            v = dw[c][i+1][1]
            val = dw[c][i+1][0] - dw[c][i][0]
            es[u].append((val, v))
            es[v].append((-val, u))
            tmp += val
            if mind[v]<tmp:
                return False
#     print(es)
#     print(dw)
    vals = [None]*h
    for start in range(h):
        if vals[start] is not None:
            continue
        q = [start]
        vals[start] = 0
        l = [(0, mind[start])]
        while q:
            u = q.pop()
            for d,v in es[u]:
                if vals[v] is None:
                    vals[v] = vals[u] + d
                    l.append((vals[v], mind[v]))
                    q.append(v)
                elif vals[v]!=vals[u]+d:
                    return False
        l.sort()
        for i in range(len(l)):
            if l[i][1]<l[i][0]-l[0][0]:
                return False
#     for u in range(h):
#         for d,v in es[u]:
#             if vals[u]+d!=vals[v]:
#                 return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
class UFP():
    def __init__(self, num):
        self.par = [-1]*num
        self.dist = [0]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            res = 0
            xo = x
            while self.par[x] >= 0:
                res += self.dist[x]
                x = self.par[x]
            self.dist[xo] = res
            self.par[xo] = x
            return x
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
                x, y = y, x
                d = -d
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
            return True
        else:
            if d + self.dist[x] - self.dist[y]:
                return False
            return True           
    
INF = 3*10**9
def check():
    H, W = map(int, readline().split())
    N = int(readline())
    Hm = [INF]*H
    Wm = [INF]*W
    HP = [[] for _ in range(H)]
    WP = [[] for _ in range(W)]
    for _ in range(N):
        h, w, a = map(int, readline().split())
        h -= 1
        w -= 1
        Hm[h] = min(Hm[h], a)
        Wm[w] = min(Wm[w], a)
        HP[h].append((w, a))
        WP[w].append((h, a))
        
    Th = UFP(H)
    Tw = UFP(W)
    for h in range(H):
        L = len(HP[h]) 
        if L > 1:
            HP[h].sort()
            for i in range(L-1):
                wp, ap = HP[h][i]
                wn, an = HP[h][i+1]
                if not Tw.union(wp, wn, an-ap):
                    return False
    for w in range(W):
        L = len(WP[w]) 
        if L > 1:
            WP[w].sort()
            for i in range(L-1):
                hp, ap = WP[w][i]
                hn, an = WP[w][i+1]
                if not Th.union(hp, hn, an-ap):
                    return False
    
    cmh = [INF]*H
    for h in range(H):
        rh = Th.find(h)
        cmh[rh] = min(cmh[rh], Th.dist[h])
    cmw = [INF]*W
    for w in range(W):
        rw = Tw.find(w)
        cmw[rw] = min(cmw[rw], Tw.dist[w])
    
    for h in range(H):
        if Hm[h] - Th.dist[h] + cmh[Th.find(h)] < 0:
            return False
    for w in range(W):
        if Wm[w] - Tw.dist[w] + cmw[Tw.find(w)] < 0:
            return False
    return True

print('Yes' if check() else 'No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
n = int(input())
G = [[] for _ in range(R+C)]
for _ in range(n):
  r, c, a = map(int, input().split())
  r -= 1
  c -= 1
  G[r].append((R+c, a))
  G[R+c].append((r, a))
D = [-1]*(R+C)
def dfs(v):
  rmin, cmin = float("inf"), float("inf")
  stack = [(v, 0)]
  while stack:
    nv, cost = stack.pop()
    D[nv] = cost
    if nv<R:
      rmin = min(rmin, cost)
    else:
      cmin = min(cmin, cost)
    for i, nc in G[nv]:
      if D[i] != -1:
        if D[nv]+D[i] != nc:
          return False
      else:
        stack.append((i, nc-D[nv]))
  return rmin+cmin >= 0

for i in range(R+C):
  if D[i] == -1:
    if not dfs(i):
      print("No")
      break
else:
  print("Yes")

Submission status: Accepted

Solution code:
# 重み付き UnionFind を初めて書いた


class WeightedUnionFind:
    # https://qiita.com/drken/items/cce6fc5c579051e64fab
    def __init__(self, n, SUM_UNITY=0):
        self.par = list(range(n))
        self.rank = [0] * n
        self.diff_weight = [SUM_UNITY] * n

    def root(self, x):
        p = self.par[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.diff_weight[x] += self.diff_weight[p]
            self.par[x] = r
            return r

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y, w):
        if self.same(x, y):
            return self.diff(x, y) == w
        w += self.weight(x);  w -= self.weight(y)
        x, y = self.root(x), self.root(y)
        # if x == y:
        #     return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight(y) - self.weight(x)

    def get_roots_weights(self):
        roots = []
        weights = []
        for x in range(len(self.par)):
            roots.append(self.root(x))
            weights.append(self.weight(x))
        return roots, weights

import sys
from operator import itemgetter
from itertools import groupby
from collections import defaultdict

def main():
    R, C = map(int, input().split())
    N = int(input())
    RCA = list(zip(*[iter(map(int, sys.stdin.read().split()))]*3))
    uf_r = WeightedUnionFind(R+1)
    uf_c = WeightedUnionFind(C+1)

    RCA.sort(key=itemgetter(0))
    for _, g in groupby(RCA, key=itemgetter(0)):
        _, c0, a0 = next(g)
        for _, c, a in g:
            if not uf_c.unite(c0, c, a-a0):
                print("No")
                exit()

    RCA.sort(key=itemgetter(1))
    for _, g in groupby(RCA, key=itemgetter(1)):
        r0, _, a0 = next(g)
        for r, _, a in g:
            if not uf_r.unite(r0, r, a-a0):
                print("No")
                exit()

    r_roots, r_weights = uf_r.get_roots_weights()
    c_roots, c_weights = uf_c.get_roots_weights()
    r_roots_inv = defaultdict(list)
    for i, r in enumerate(r_roots):
        r_roots_inv[r].append(i)
    c_roots_inv = defaultdict(list)
    for i, r in enumerate(c_roots):
        c_roots_inv[r].append(i)
    Closed_r = set()
    Closed_c = set()
    for r, c, a in RCA:
        root_r, root_c = r_roots[r], c_roots[c]
        if root_r in Closed_r:
            assert root_c in Closed_c
            continue
        Closed_r.add(root_r)
        Closed_c.add(root_c)
        mi = float("inf")
        for v in r_roots_inv[root_r]:
            mi = min(mi, r_weights[v])
        a += mi - r_weights[r]
        for v in c_roots_inv[root_c]:
            a_ = a + c_weights[v] - c_weights[c]
            if a_ < 0:
                print("No")
                exit()
    print("Yes")

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

R,C = map(int,input().split())
N = int(input())
RCA = [tuple(int(x) for x in input().split()) for _ in range(N)]

# 二部グラフ
graph = [[] for _ in range(R+C)]
for r,c,a in RCA:
    graph[r-1].append((R+c-1,a))
    graph[R+c-1].append((r-1,a))

graph

# グラフの頂点に値を割り当てて、頂点の重みの和が辺の重みになるようにする。
wt_temp = [None] * (R+C)
wt = [None] * (R+C)
for x in range(R+C):
    if wt_temp[x] is not None:
        continue
    wt_temp[x] = 0
    min_wt_row = 0
    q = [x]
    while q:
        y = q.pop()
        for z,a in graph[y]:
            if wt_temp[z] is not None:
                continue
            wt_temp[z] = a - wt_temp[y]
            q.append(z)
            if z<R and min_wt_row > wt_temp[z]:
                min_wt_row = wt_temp[z]
    wt[x] = -min_wt_row
    q = [x]
    while q:
        y = q.pop()
        for z,a in graph[y]:
            if wt[z] is not None:
                continue
            wt[z] = a - wt[y]
            q.append(z)

bl = True
if any(x<0 for x in wt):
    bl = False
for r,c,a in RCA:
    if wt[r-1] + wt[R+c-1] != a:
        bl = False

answer = 'Yes' if bl else 'No'
print(answer)