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

Solution code:
R, C = map(int, raw_input().split())
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]
P.sort()
dic = {}
for x, y, a in P:
    dic[x, y] = a

for i in xrange(n):
    x, y, a = s = P[i]
    for j in xrange(i+1, n):
        z, w, b = t = P[j]
        if s[0] == t[0]:
            continue
        if (x, w) in dic and (z, y) in dic:
            if dic[x, y] + dic[z, w] != dic[x, w] + dic[z, y]:
                print "No"
                exit(0)
print "Yes"

Submission status: Wrong Answer

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

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

d = defaultdict(list)

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

V = dict()
V["R", 0] = 0

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

walk(("R", 0))


if min(a for (v, a) in V.items() if v[0] == "R") + min(a for (v, a) in V.items() if v[0] == "C") >= 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
print('Yes');

Submission status: Wrong Answer

Solution code:
import sys

R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
Grid = [[-1 for i in range(C)] for j in range(R)] ## Grid[r][c]

for i in range(N):
    x, y, z = map(int, input().split())
    r.append(x - 1)
    c.append(y - 1)
    a.append(z)
    Grid[x - 1][y - 1] = z

if -1 in Grid:
    print(Grid.index(-1))

for i in range(R - 1):
    for j in range(C - 1):
        t = [0 for k in range(4)]
        t[0] = Grid[i][j]
        t[1] = Grid[i+1][j]
        t[2] = Grid[i][j+1]
        t[3] = Grid[i+1][j+1]

        if t.count(-1) > 1:
            continue
        if t.count(-1) == 1:
            index = t.index(-1)
            if index == 0:
                t[0] = t[1] + t[2] - t[3]
            elif index == 1:
                t[1] = t[0] + t[3] - t[2]
            elif index == 2:
                t[2] = t[0] + t[3] - t[1]
            elif index == 3:
                t[3] = t[1] + t[2] - t[0]


        for k in range(4):
            if t[k] < 0:
                print('NO')
                sys.exit()

        Grid[i][j] = t[0]
        Grid[i+1][j] = t[1]
        Grid[i][j+1] = t[2]
        Grid[i+1][j+1] = t[3]

        if t.count(-1) == 0 and Grid[i][j] + Grid[i+1][j+1] != Grid[i][j+1] + Grid[i+1][j]:
            print('NO')
            sys.exit()



flg = 1
for i in range(R):
    if -1 in Grid[i] and flg == 1:
        print('NO')
        flg = 0

if flg == 1:
    print('YES')

Submission status: Wrong Answer

Solution code:
R, C = map(int, input().split())
N = int(input())
M = dict()
for n in range(N):
    r, c, a = map(int, input().split())
    M[(r - 1, c - 1)] = a


def square(r, c):
    return (
        (r    , c),
        (r + 1, c),
        (r + 1, c + 1),
        (r    , c + 1)
    )

def iter_square(pos):
    r, c = pos
    if r != 0 and c != 0:
        yield square(r - 1, c - 1)
    if r != 0 and c + 1 < C:
        yield square(r - 1, c)
    if c != 0 and r + 1 < R:
        yield square(r    , c - 1)
    if r + 1 < R and c + 1 < C:
        yield square(r, c)

def pred_first(pred, iterable):
    for item in iterable:
        if pred(item):
            return item

def rev_side(i):
    return (i + 2) % 4


def check():
    stack = [pos for pos in M.keys()]
    while stack:
        pos = stack.pop()
        for sq in iter_square(pos):
            n_filled = sum(1 for pos in sq if pos in M)
            if n_filled == 3:
                if sq[0] in M and sq[2] in M:
                    s = M[sq[0]] + M[sq[2]]
                else:
                    s = M[sq[1]] + M[sq[3]]
                i, target_pos = pred_first(lambda i: i[1] not in M, enumerate(sq))
                rev_pos = sq[rev_side(i)]

                s -= M[rev_pos]
                if s < 0:
                    return False
                stack.append(target_pos)
                M[target_pos] = s

            if n_filled == 4:
                if M[sq[0]] + M[sq[2]] != M[sq[1]] + M[sq[3]]:
                    return False


    return True
if check():
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def checker(board):
    #for (upper,under) in zip(board[0],board[1])
    upper = board[0]
    under = board[1]
    numlist = []
    for i in range(len(upper)-2):
        try:
            tmp = upper[i] + under[i+1]
            numlist.append(tmp)
            tmp2 = upper[i+1] + under[i]
            numlist.append(tmp2)
        except:
            pass

    if len(list(set(numlist))) == 1:
        return 'Yes'
    else:
        return 'No'


R,C = map(int,raw_input().split())
N = input()

a = []
for i in xrange(N):
    a.append(map(int,raw_input().split()))

#matrix
ans_board =	[['None' for i in xrange(C)],
         ['None' for i in xrange(C)]]

for a_sub in a:
    ans_board[a_sub[0]-1][a_sub[1]-1] = a_sub[2]

print checker(ans_board)

Submission status: Wrong Answer

Solution code:
def work():
    r, c = map(int, raw_input().split())
    n = int(raw_input())
    table = [[None] * c for _ in xrange(r)]
    diff = [None] * (r-1)
    if n == r*c:
        return 'No'
    for i in xrange(n):
        x, y, z = map(int, raw_input().split())
        table[x-1][y-1] = z
        if x < r and table[x][y-1] is not None:
            if diff[x-1] is None:
                diff[x-1] = table[x][y-1] - table[x-1][y-1]
            elif table[x][y-1] - table[x-1][y-1] != diff[x-1]:
                return 'No'
        if x > 1 and table[x-2][y-1] is not None:
            if diff[x-2] is None:
                diff[x-2] = table[x-1][y-1] - table[x-2][y-1]
            elif table[x-1][y-1] - table[x-2][y-1] != diff[x-2]:
                return 'No'
    for ii in xrange(r - 1):
        if diff[ii] is None:
            continue
        for jj in xrange(c):
            if table[ii][jj] and table[ii+1][jj]:
                if table[ii+1][jj] - table[ii][jj] != diff[ii]:
                    return 'No'
            elif table[ii][jj]:
                if table[ii][jj] + diff[ii] < 0:
                    return 'No'
            elif table[ii+1][jj]:
                if table[ii+1][jj] - diff[ii] < 0:
                    return 'No'
    return 'Yes'


print work()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 24 21:51:15 2016

@author: dotha
"""

def squarecheck(square):
    #明らかなところがあれば埋める
    if None not in square:
        return (square[0]+square[2]==square[1]+square[3], square, False)
    elif square.count(None)==1:
        if square[0] == None:
            square[0] = square[1]+square[3]-square[2]
            if square[0] < 0:
                return (False, square, False)
        elif square[1] == None:
            square[1] = square[0]+square[2]-square[3]
            if square[1] < 0:
                return (False, square, False)
        elif square[2] == None:
            square[2] = square[1]+square[3]-square[0]
            if square[2] < 0:
                return (False, square, False)
        else:
            square[3] = square[0]+square[2]-square[1]
            if square[3] < 0:
                return (False, square, False)
        return (True, square, True)
    else:
        return(True,square, False)

def clearcheck(table,R,C):
    Done = False
    somethinghappened = False
    for tate in range(R-1):
        for yoko in range(C-1):
            (ccheck,square, Done) = squarecheck([table[tate][yoko],\
            table[tate][yoko+1],table[tate+1][yoko+1],\
            table[tate+1][yoko]])
            if Done:
                somethinghappened == True
            if ccheck==False:
                return False, table, False
            table[tate][yoko]=square[0]
            table[tate][yoko+1]=square[1]
            table[tate+1][yoko+1]=square[2]
            table[tate+1][yoko]=square[3]
    return True, table, somethinghappened

def main():
    R,C = tuple(map(int,input().split()))
    N = int(input())
    if N==R*C:
        print('No')
        return
    else:
        table = [[None for i in range(C)] for j in range(R)]
    for i in range(N):
        r,c,a = tuple(map(int,input().split()))
        table[r-1][c-1] = a
    while True:
        success, table, done = clearcheck(table,R,C)
        if success == False:
            print('No')
            return
        if done==False:
            break
    print('Yes')
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
r,c=input().split()
r=int(r)
c=int(c)
n=int(input())
arr = [[-1 for i in range(c)] for j in range(r)]
for i in range(n):
 j,k,l=input().split()
 arr[int(j)-1][int(k)-1]=int(l)

res=True
for i in range(r-1):
 d=10000000000
 for j in range(c):
  if (arr[i][j]==-1) or (arr[i+1][j]==-1):
   continue
  elif d==10000000000:
   d=arr[i][j]-arr[i+1][j]
  else:
   if arr[i][j]-arr[i+1][j]!=d:
    res=False
    break
  if not res:
   break
for j in range(c-1):
 d=10000000000
 for i in range(j):
  if (arr[i][j]==-1) or (arr[i][j+1]==-1):
   continue
  elif d==10000000000:
   d=arr[i][j]-arr[i][j+1]
  else:
   if arr[i][j]-arr[i][j+1]!=d:
    res=False
    break
  if not res:
   break
if res:
 print("Yes")
else:
 print("No")

Submission status: Wrong Answer

Solution code:
def work():
    r, c = map(int, raw_input().split())
    n = int(raw_input())
    table = [[None] * c for _ in xrange(r)]
    diff = [None] * (r-1)
    for i in xrange(n):
        x, y, z = map(int, raw_input().split())
        table[x-1][y-1] = z
        if x < r and table[x][y-1] is not None:
            if diff[x-1] is None:
                diff[x-1] = table[x][y-1] - table[x-1][y-1]
            elif table[x][y-1] - table[x-1][y-1] != diff[x-1]:
                return 'No'
        if x > 1 and table[x-2][y-1] is not None:
            if diff[x-2] is None:
                diff[x-2] = table[x-1][y-1] - table[x-2][y-1]
            elif table[x-1][y-1] - table[x-2][y-1] != diff[x-2]:
                return 'No'
    for ii in xrange(r - 1):
        if diff[ii] is None:
            continue
        for jj in xrange(c):
            if table[ii][jj] and table[ii+1][jj]:
                if table[ii+1][jj] - table[ii][jj] != diff[ii]:
                    return 'No'
            elif table[ii][jj]:
                if table[ii][jj] + diff[ii] < 0:
                    return 'No'
            elif table[ii+1][jj]:
                if table[ii+1][jj] - diff[ii] < 0:
                    return 'No'
    return 'Yes'


print work()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 24 21:51:15 2016

@author: dotha
"""

def clear():
    pass

def squarecheck(square):
    #明らかなところがあれば埋める
    if None not in square:
        return (square[0]+square[2]==square[1]+square[3], square, False)
    elif square.count(None)==1:
        if square[0] == None:
            square[0] = square[1]+square[3]-square[2]
            if square[0] < 0:
                return (False, square, False)
        elif square[1] == None:
            square[1] = square[0]+square[2]-square[3]
            if square[1] < 0:
                return (False, square, False)
        elif square[2] == None:
            square[2] = square[1]+square[3]-square[0]
            if square[2] < 0:
                return (False, square, False)
        else:
            square[3] = square[0]+square[2]-square[1]
            if square[3] < 0:
                return (False, square, False)
        return (True, square, True)
    else:
        return(True,square)

def clearcheck(table,R,C):
    Done = False
    somethinghappened = False
    for tate in range(R-1):
        for yoko in range(C-1):
            (ccheck,square, Done) = squarecheck([table[tate][yoko],\
            table[tate][yoko+1],table[tate+1][yoko+1],\
            table[tate+1][yoko]])
            if Done:
                somethinghappened == True
            if ccheck==False:
                return False, table, False
            table[tate][yoko]=square[0]
            table[tate][yoko+1]=square[1]
            table[tate+1][yoko+1]=square[2]
            table[tate+1][yoko]=square[3]
    return True, table, somethinghappened

def main():
    R,C = tuple(map(int,input().split()))
    N = int(input())
    if N==R*C:
        print('No')
        return
    else:
        table = [[None for i in range(C)] for j in range(R)]
    for i in range(N):
        r,c,a = tuple(map(int,input().split()))
        table[r-1][c-1] = a
    while True:
        success, table, done = clearcheck(table,R,C)
        if success == False:
            print('No')
            return
        if done==False:
            break
    print('Yes')
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print "Yes"

Submission status: Wrong Answer

Solution code:
from random import *
print(choice(["Yes","No"]))

Submission status: Wrong Answer

Solution code:
R,C = map(int,raw_input().split(" "))
N = input()
inputs = []
rs = set()
cs = set()
for i in range(N):
    r,c,a = map(int,raw_input().split(" "))
    inputs.append((r,c,a))
    rs.add(r)
    cs.add(c)
rs = list(rs)
cs = list(cs)
rs.sort()
cs.sort()


rss = {r:i for i,r in enumerate(rs)}
css = {c:i for i,c in enumerate(cs)}

nfld = [[-1 for j in range(len(cs))] for i in range(len(rs))]

for i in range(N):
    r,c,a = inputs[i]
    nfld[rss[r]][css[c]] = a


RR = len(rs)
CC = len(cs)

def foo():
    for r in range(RR-1):
        for c in range(CC-1):
            sl1 = -1
            sl2 = -1
            
            slf1 = 0
            slf2 = 0
            if nfld[r][c]>=0 and nfld[r+1][c+1]>=0:
                sl1 = nfld[r][c] + nfld[r+1][c+1]
                slf1 = 3



            if nfld[r+1][c] >= 0 and nfld[r][c+1]>=0:
                sl2 = nfld[r+1][c] + nfld[r][c+1]
                slf2 = 3

            if slf1 == 3 and slf2 == 3:
                if sl1 != sl2:
                    return False

            elif slf1==3:
                 if nfld[r+1][c] >= 0:
                     if slf1-nfld[r+1][c]<0:
                         return False
                 elif nfld[r][c+1]>=0:
                    if slf1-nfld[r][c+1]<0:
                        return False
            elif slf2 == 3:
                 if nfld[r][c] >= 0:
                     if slf2-nfld[r][c]<0:
                         return False
                 elif nfld[r+1][c+1]>=0:
                    if slf2-nfld[r+1][c+1]<0:
                        return False

    return True

print "YES" if foo() else "NO"

Submission status: Wrong Answer

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

import numpy as np
import sys

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)]
        if len(set(diffs)) > 1:
            print "No"
            sys.exit()
        diff = max(diffs) if (mat[i] > 0).any() else 0
    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: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########
 
rr,cc = ii()
n=i()
r,c,a=[0]*n,[0]*n,[0]*n
for j in range(n):
    r[j],c[j],a[j] = ii()

m=[[(-1) for j in range(cc)] for k in range(rr)]

def four(mr,mc):
    cnt=0
    su=0
    xx=0
    yy=0
    for j in range(2):
        for k in range(2):
            if m[mr+j][mc+k]==-1:
                cnt+=1
                xx=mr+j
                yy=mc+k
            else:
                su+=m[mr+j][mc+k]
    if cnt==1:
        return dfs(xx,yy,-su)
    elif cnt==0 and su!=0:
        return -1
    else:
        return 0
    
def dfs(mr,mc,ma):
    if ma<0 or  m[mr][mc]!=-1:
        return -1
    else:
        stat=0
        m[mr][mc] = (-1)**(mr+mc)*ma
        if mr!=0 and mc!=0:
            stat+=four(mr-1,mc-1)
        if mr!=0 and mc!=cc-1:
                stat+=four(mr-1,mc)
        if mr!=rr-1 and mc!=0:
            stat+=four(mr,mc-1)
        if mr!=rr-1 and mc!=cc-1:
            stat+=four(mr,mc)
        if stat<0:
            return -1
        else:
            return 0

for j in range(n):
    x=dfs(r[j]-1,c[j]-1,a[j])
    if x==-1:
        print "No"
        break
else:
    print "Yes"

Submission status: Wrong Answer

Solution code:
import sys

R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
Grid = [[-1 for i in range(C)] for j in range(R)] ## Grid[r][c]

for i in range(N):
    x, y, z = map(int, input().split())
    r.append(x - 1)
    c.append(y - 1)
    a.append(z)
    Grid[x - 1][y - 1] = z

for i in range(R - 1):
    for j in range(C - 1):
        t = [0 for k in range(4)]
        t[0] = Grid[i][j]
        t[1] = Grid[i+1][j]
        t[2] = Grid[i][j+1]
        t[3] = Grid[i+1][j+1]

        if t.count(-1) > 1:
            continue
        if t.count(-1) == 1:
            index = t.index(-1)
            if index == 0:
                t[0] = t[1] + t[2] - t[3]
            elif index == 1:
                t[1] = t[0] + t[3] - t[2]
            elif index == 2:
                t[2] = t[0] + t[3] - t[1]
            elif index == 3:
                t[3] = t[1] + t[2] - t[0]


        for k in range(4):
            if t[k] < 0:
                print('NO')
                sys.exit()

        Grid[i][j] = t[0]
        Grid[i+1][j] = t[1]
        Grid[i][j+1] = t[2]
        Grid[i+1][j+1] = t[3]

        if t.count(-1) == 0 and Grid[i][j] + Grid[i+1][j+1] != Grid[i][j+1] + Grid[i+1][j]:
            print('NO')
            sys.exit()



flg = 1
for i in range(R):
    if -1 in Grid[i] and flg == 1:
        print('NO')
        flg = 0

if flg == 1:
    print('YES')

Submission status: Wrong Answer

Solution code:
def work(table):
    for ii in xrange(r - 1):
        diff = None
        for jj in xrange(c):
            if table[ii][jj] is not None and table[ii+1][jj] is not None:
                diff = table[ii+1][jj] - table[ii][jj]
                break
        if diff is None:
            continue
        for jj in xrange(c):
            if table[ii][jj] and table[ii+1][jj]:
                if table[ii+1][jj] - table[ii][jj] != diff:
                    return 'No'
            elif table[ii][jj]:
                if table[ii][jj] + diff < 0:
                    return 'No'
            elif table[ii+1][jj]:
                if table[ii+1][jj] - diff < 0:
                    return 'No'
    return 'Yes'


r, c = map(int, raw_input().split())
n = int(raw_input())
table = [[None] * c for _ in xrange(r)]
for i in xrange(n):
    x, y, z = map(int, raw_input().split())
    table[x-1][y-1] = z
print work(table)

Submission status: Wrong Answer

Solution code:
import sys
r, c = map(int, raw_input().split())
n = int(raw_input())
table = [[None] * c for _ in xrange(r)]
for i in xrange(n):
    x, y, z = map(int, raw_input().split())
    table[x-1][y-1] = z
for ii in xrange(r - 1):
    diff = None
    for jj in xrange(c):
        if table[ii][jj] is not None and table[ii+1][jj] is not None:
            diff = table[ii+1][jj] - table[ii][jj]
            break
    if diff is None:
        continue
    for jj in xrange(c):
        if table[ii][jj] and table[ii+1][jj]:
            if table[ii+1][jj] - table[ii][jj] != diff:
                print 'No'
                sys.exit()
        elif table[ii][jj]:
            if table[ii][jj] + diff < 0:
                print 'No'
                sys.exit()
        elif table[ii+1][jj]:
            if table[ii+1][jj] - diff < 0:
                print 'No'
                sys.exit()
print 'Yes'

Submission status: Wrong Answer

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

nq = int(raw_input())
points = {}
for i in range(nq):
    r, c, a = map(int, raw_input().split())
    key = (r - 1) * m + c - 1
    points[key] = a
    
feasible = True
dr, dc = [ 0, 1, 1 ], [ 1, 0, 1 ]
updated = True
count = 0
while updated and count < 10:
    count += 1
    updated = False
    keys = points.keys()
    for key in keys:
        a = points[key]
        r, c = key // m, key % m
        if r == n - 1 or c == m - 1:
            continue
        xs = 3 * [ None ]
        ys = 3 * [ None ]
        for i in range(3):
            xs[i] = x = (r + dr[i])*m + c + dc[i]
            if x in points:
                ys[i] = points[x]
        b, c, d = ys
        if c != None and d != None:
            if c > a + d:
                feasible = False
                break
            if b != None:
                if a + d != b + c:
                    feasible = False
                    break
                continue
            points[xs[0]] = a + d - c
            #print('update b %d' % (xs[0]))
            updated = True
            continue
        if b != None and c != None:
            if a > b + c:
                feasible = False
                break
            points[xs[2]] = b + c - a
            #print('update d %d' % (xs[2]))
            updated = True
            continue
        if b != None and d != None:
            if b > a + d:
                feasible = False
                break
            points[xs[1]] = a + d - b
            #print('update c %d' % (xs[1]))
            updated = True
            continue

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

Submission status: Wrong Answer

Solution code:
import sys

R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
Grid = [[-1 for i in range(C)] for j in range(R)] ## Grid[r][c]

for i in range(N):
    x, y, z = map(int, input().split())
    r.append(x - 1)
    c.append(y - 1)
    a.append(z)
    Grid[x - 1][y - 1] = z

for i in range(R - 1):
    for j in range(C - 1):
        t = [0 for k in range(4)]
        t[0] = Grid[i][j]
        t[1] = Grid[i+1][j]
        t[2] = Grid[i][j+1]
        t[3] = Grid[i+1][j+1]

        if t.count(-1) > 1:
            continue
        if t.count(-1) == 1:
            index = t.index(-1)
            if index == 0:
                Grid[i][j] = t[1] + t[2] - t[0]
            elif index == 1:
                Grid[i+1][j] = t[0] + t[3] - t[2]
            elif index == 2:
                Grid[i][j+1] = t[0] + t[3] - t[1]
            elif index == 3:
                Grid[i+1][j+1] = t[1] + t[2] - t[3]

        if Grid[i][j] + Grid[i+1][j+1] != Grid[i][j+1] + Grid[i+1][j]:
            print('NO')
            sys.exit()



flg = 1
for i in range(R):
    if -1 in Grid[i] and flg == 1:
        print('NO')
        flg = 0

if flg == 1:
    print('YES')

Submission status: Wrong Answer

Solution code:
import numpy as np
R, C = map(int, raw_input().split())
N = int(raw_input())
mat = np.zeros((R, C), dtype='int')
mat_2 = np.zeros((R, C), dtype='int')
for i in range(N):
    r, c, a = map(int, raw_input().split())
    mat[r-1, c-1] = a
    mat_2[r-1, c-1] = 1

sol = "YES"
for r in range(R - 1):
    # make list of lag
    lag_list = [(mat[r + 1, c] - mat[r, c]) * (2*(c % 2) - 1) for c in range(C) if mat_2[r + 1, c] * mat_2[r, c] == 1]
    if len(lag_list) > 0:
        if len(list(set(lag_list))) > 1:
            sol = "NO"
for c in range(C - 1):
    # make list of lag
    lag_list = [(mat[r, c + 1] - mat[r, c]) * (2*(r % 2) - 1) for r in range(R) if mat_2[r, c + 1] * mat_2[r, c] == 1]
    if len(lag_list) > 0:
        if len(list(set(lag_list))) > 1:
            sol = "NO"
print sol

Submission status: Wrong Answer

Solution code:
print("Yes")

Submission status: Time Limit Exceeded

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
        while q:
            u = q.pop()
            for d,v in es[u]:
                if vals[v] is None:
                    vals[v] = vals[u] + d
                    q.append(v)
                elif vals[v]!=vals[u]+d:
                    return False
                else:
                    q.append(v)
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
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(VectorSet):
	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: Time Limit Exceeded

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