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: Accepted

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

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

R, C = map(int, input().split())
N = int(input())
VectorSet = set()
Grid = defaultdict(list)
for i in range(N):
	r, c, a = map(int, input().split())
	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: Accepted

Solution code:
from collections import deque
r, c = map(int, raw_input().split())
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]

d = {}
P.sort()
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if r1 == r2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
P.sort(key=lambda (r,c,a): (c,r))
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if c1 == c2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
m = {}
for i, (r0, c0, a0) in enumerate(P):
    m[r0, c0] = (a0, i)
used = [0]*n
for i in xrange(n):
    if not used[i]:
        r0, c0, base = P[i]

        used[i] = 1
        deq = deque()
        deq.append((r0, c0, base))
        rs = {r0: 0}
        cs = {c0: 0}

        while deq:
            r0, c0, now = deq.popleft()

            for (r1, c1), diff in d.get((r0, c0), []):
                a1, j = m[r1, c1]
                if r0 == r1:
                    if not used[j]:
                        cs[c1] = cs[c0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if cs[c0] + diff != cs[c1]:
                            print "No"
                            exit(0)
                else:
                    if not used[j]:
                        rs[r1] = rs[r0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if rs[r0] + diff != rs[r1]:
                            print "No"
                            exit(0)
        rmin = min(rs.values())
        cmin = min(cs.values())
        if rmin + cmin + base < 0:
            print "No"
            exit(0)
print "Yes"

Submission status: Accepted

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

class Edge:
	def __init__(self, v1, v2, w):
		self.v1 = v1
		self.v2 = v2
		self.w = w
	def __repr__(self):
		return 'Edges({},{},{})'.format(self.v1, self.v2, self.w)

def dfs(edges, v, visited, i, m, r):
	m[0 if i<r else 1] = min(m[0 if i<r else 1], v[i])
	for edge in edges[i]:
		if visited[edge.v2]:
			if (v[i] + v[edge.v2]) != edge.w:
				return False
			continue
		visited[edge.v2] = True
		v[edge.v2] = edge.w - v[i]
		if not dfs(edges, v, visited, edge.v2, m, r):
			return False
	return True

r, c = map(int, input().split())
edges = [list() for _ in range(r + c)]
v = [0] * (r + c)
visited = [False] * (r + c)
n = int(input())
for _ in range(n):
	ri, ci, ai = map(int, input().split())
	ri, ci = ri-1, ci-1
	edges[ri].append(Edge(ri, r+ci, ai))
	edges[r+ci].append(Edge(r+ci, ri, ai))

flag = True
for i in range(r + c):
	if visited[i]:
		continue
	m = [10**10, 10**10]
	if (not dfs(edges, v, visited, i, m, r)) or sum(m) < 0:
		flag = False
if flag:
	print('Yes')
else:
	print('No')

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    r, c = map(int, stdin.readline().split())
    n = int(stdin.readline())
    a = map(int, stdin.read().split(), repeat(10, 3 * n))
    rs = [[] for i in xrange(c)]
    cs = [[] for i in xrange(r)]
    for i in xrange(n):
        a[i*3] -= 1
        y = a[i*3]
        a[i*3+1] -= 1
        x = a[i*3+1]
        rs[x].append((y, a[i*3+2]))
        cs[y].append((x, a[i*3+2]))
    v = [None] * c
    rd = [None] * r
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(c):
        if v[i] is not None:
            continue
        if not rs[i]:
            continue
        mnc = rs[i][0][1]
        pu((rs[i][0][0], rs[i][0][1], i, 0))
        mnr = 0
        while st:
            y, base, x, dr = po()
            for nx, val in cs[y]:
                tmp = val - dr
                if v[nx] is None:
                    v[nx] = tmp
                    if mnc > tmp:
                           mnc = tmp
                    for ny, nval in rs[nx]:
                        if not rd[ny]:
                            rd[ny] = 1
                            if 0 > nval - tmp < -mnr:
                                mnr = tmp - nval
                            pu((ny, nval, nx, nval - tmp))
                elif v[nx] != tmp:
                    print "No"
                    return
        if mnc < mnr:
            print "No"
            return
    print "Yes"
main()

Submission status: Runtime Error

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
    for u in range(h):
        for d,v in es[u]:
            if vals[u]+d!=vals[v]:
                return False
    hoge
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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
        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: Runtime Error

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**18] * 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
    assert False
    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
                elif vals[v]!=vals[u]+d:
                    return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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


# ファイル読み込み
def _input():
    lines = open("../tmp_in").readlines()
    for ss in lines:
        yield ss.rstrip()
input = _input().__next__

h,w = list(map(int, input().split()))
n = int(input())
from collections import defaultdict
mind = [10**18] * 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
                elif vals[v]!=vals[u]+d:
                    return False
    return True
ans = main()
if ans:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool solve(int R, int C){
    vector<vector<pair<int, int>>> gr(R), gc(C);
    int N; cin >> N;
    for(int i=0;i<N;i++){
        int r, c, a; cin >> r >> c >> a;
        gr[r-1].emplace_back(c-1, a);
        gc[c-1].emplace_back(r-1, a);
    }
    vector<int> dif(R), check(R, 0);
    for(int i=0;i<R;i++){
        if(check[i]) continue;
        dif[i] = 0;
        check[i] = 1;
        int m = 1000000000;
        int md = dif[i];
        queue<int> qu; qu.push(i);
        while(!qu.empty()){
            int p = qu.front(); qu.pop();
            for(auto c : gr[p]){
                int val = c.second;
                for(auto r : gc[c.first]){
                    int d = r.second - c.second + dif[p];
                    if(!check[r.first]){
                        check[r.first] = 1;
                        dif[r.first] = d;
                        qu.push(r.first);
                    }
                    if(dif[r.first] != d) return false;
                    md = min(d, md);
                    m = min(m, r.second - d);
                }
            }
        }
        if(m + md < 0) return false;
    }
    return true;
}

int main(){
    int R, C;
    while(cin >> R >> C){
        cout << (solve(R, C) ? "Yes" : "No") << endl;
    }
}

Submission status: Runtime Error

Solution code:
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()
    assert False
    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[root_r]
        for v in c_roots_inv[root_c]:
            a_ = a + c_weights[v] - c_weights[root_c]
            if a_ < 0:
                print("No")
                exit()
    print("Yes")

main()

Submission status: Runtime Error

Solution code:
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[root_r]
        for v in c_roots_inv[root_c]:
            a_ = a + c_weights[v] - c_weights[root_c]
            if a_ < 0:
                print("No")
                exit()
    assert False
    print("Yes")

main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
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: Runtime Error

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

R, C = map(int, input().split())
N = int(input())
r = []
c = []
a = []
for i in range(N):
	ri, ci, ai = map(int, input().split())
    	r.append(ri)
    	c.append(ci)
    	a.append(ai)
x = {}
y = {}
     
for i in range(N):
  	if r[i] in x:
   		if c[i] in y:
   			if x[r[i]] + y[c[i]] != a[i]:
   				print("No")
   				break
  		else:
   			y[c[i]] = a[i] - x[r[i]]
   	else:
   		if c[i] in y:
   			x[r[i]] = a[i] - y[c[i]]
   		else:
   			x[r[i]] = a[i]
   			y[c[i]] = 0
    
else:
   	if min(y.values()) + min(x.values()) >= 0:
   		print("Yes")
   	else:
   		print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import copy

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

(R, C) = readInput()
N = int(input())
rowIdx = set() 
cover = set()
grid = defaultdict(lambda:None)
rowGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	grid[(r, c)] = a 
	rowIdx.add(r)

pairIdx = copy.copy(rowIdx)	
for i in rowIdx:
	tempRow = rowGrid[i]
	tempRow.difference_update(cover)
	if (len(tempRow) is 0):
		continue
	pairIdx.remove(i)
	for j in pairIdx:
		tempPair = rowGrid[j]
		mark = 1
		for k in tempRow:
			if (grid[(j, k)] is now None):
				diff = grid[(i, k)] - grid[(j, k)]
				mark = 0 
				break
		if (mark is 1):
			continue
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP is None and anchor < diff):
				print('No')
				exit()
			elif (anchorP is not None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP is None and anchor < -diff):
				print('No')
				exit()
	cover &= tempRow
	if (len(cover) is C):
		break
print('Yes')

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

(R, C) = readInput()
N = int(input())
rowIdx = set() 
grid = defaultdict(lambda:None)
rowGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	grid[(r, c)] = a 
	rowIdx.add(r)

pairIdx = rowIdx.copy	
for i in rowIdx:
	pairIdx.remove(i)
	for j in pairIdx:
		tempRow = rowGrid[i]
		tempPair = rowGrid[j]
		mark = 1
		for k in tempRow:
			if (grid[(j, k)] != None):
				diff = grid[(i, k)] - grid[(j, k)]
				mark = 0 
		if (mark is 1):
			continue
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP is None and anchor < diff):
				print('No')
				exit()
			elif (anchorP is not None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP is None and anchor < -diff):
				print('No')
				exit()
print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np

R, C = map(int, raw_input().split())
N = int(raw_input())
rca_list = []


for i in range(N):
    rca_list.append(map(int, raw_input().split()))
    

# ret
ret = "YES"


while len(rca_list) > 0 and ret == "YES":
    
    # 
    r_vec = np.zeros(R)
    r_vec_2 = np.zeros(R)
    c_vec = np.zeros(C)
    c_vec_2 = np.zeros(C)


    # first square
    r, c, a = rca_list.pop()

    r_vec[r-1] = a
    c_vec[c-1] = 0
    r_vec_2[r-1] = 1
    c_vec_2[c-1] = 1

    go_flg = "YES"
    while go_flg == "YES" and ret == "YES":
        go_flg = "NO"
        for i in range(len(rca_list)-1, , -1):
            r, c, a = rca_list[i]
            # filled
            if r_vec_2[r-1] + c_vec_2[c-1] == 2:
                rca_list.pop(i)
                go_flg = "YES"
                if c != r_vec[r-1] + c_vec[c-1]:
                    ret = "NO"
            elif r_vec_2[r-1] + c_vec_2[c-1] == 1:
                if r_vec_2[r-1] == 1:
                    c_vec_2[c-1] = 1
                    c_vec[c-1] = a - r_vec[r-1]
                    rca_list.pop(i)
                    go_flg = "YES"
                elif c_vec_2[c-1] == 1:
                    r_vec_2[r-1] = 1
                    r_vec[r-1] = a - c_vec[c-1]
                    rca_list.pop(i)
                    go_flg = "YES"
            else:
                pass
            
    if min(r_vec[r_vec==1]) + min(c_vec[c_vec==1]) < 0:
        ret = "NO"
    
print ret

Submission status: Runtime Error

Solution code:
r_vec = np.zeros(R)
r_vec_2 = np.zeros(R)
c_vec = np.zeros(C)
c_vec_2 = np.zeros(C)

# ret
ret = "YES"


while len(rca_list) > 0 and ret == "YES":
    # first square
    r, c, a = rca_list.pop()

    r_vec[r-1] = a
    c_vec[c-1] = 0
    r_vec_2[r-1] = 1
    c_vec_2[c-1] = 1

    go_flg = "YES"
    print r_vec, r_vec_2, c_vec, c_vec_2, go_flg, ret
    while go_flg == "YES" and ret == "YES":
        go_flg = "NO"
        for i in range(len(rca_list)-1, -1, -1):
            r, c, a = rca_list[i]
            # filled
            if r_vec_2[r-1] + c_vec_2[c-1] == 2:
                rca_list.pop(i)
                go_flg = "YES"
                print "filled" + str([r, c, a])
                if c != r_vec[r-1] + c_vec[c-1]:
                    ret = "NO"
            elif r_vec_2[r-1] + c_vec_2[c-1] == 1:
                if r_vec_2[r-1] == 1:
                    c_vec_2[c-1] = 1
                    c_vec[c-1] = a - r_vec[r-1]
                    print "one filled" + str([r, c, a])
                    rca_list.pop(i)
                    go_flg = "YES"
                elif c_vec_2[c-1] == 1:
                    r_vec_2[r-1] = 1
                    r_vec[r-1] = a - c_vec[c-1]
                    print "one filled" + str([r, c, a])
                    rca_list.pop(i)
                    go_flg = "YES"
            else:
                pass
            
if ret == "YES" and min(r_vec) + min(c_vec) >= 0:
    print "YES"
else:
    print "NO"

Submission status: Runtime Error

Solution code:
from collections import deque
r, c = map(int, raw_input().split())
n = input()
P = [map(int, raw_input().split()) for i in xrange(n)]

d = {}
P.sort()
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if r1 == r2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
P.sort(key=lambda (r,c,a): (c,r))
for i in xrange(1, n):
    r1, c1, a1 = P[i-1]
    r2, c2, a2 = P[i]
    if c1 == c2:
        d.setdefault((r1, c1), []).append(((r2, c2), a2-a1))
        d.setdefault((r2, c2), []).append(((r1, c1), a1-a2))
m = {}
for i, (r0, c0, a0) in enumerate(P):
    m[r0, c0] = (a0, i)

used = [0]*n
for i in xrange(n):
    if not used[i]:
        r0, c0, base = P[i]

        used[i] = 1
        deq = deque()
        deq.append((r0, c0, base))
        rs = {r0: 0}
        cs = {c0: 0}

        while deq:
            r0, c0, now = deq.popleft()

            for (r1, c1), diff in d[r0, c0]:
                a1, j = m[r1, c1]
                if r0 == r1:
                    if not used[j]:
                        cs[c1] = cs[c0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if cs[c0] + diff != cs[c1]:
                            print "No"
                            exit(0)
                else:
                    if not used[j]:
                        rs[r1] = rs[r0] + diff
                        used[j] = 1
                        deq.append((r1, c1, now + diff))
                    else:
                        if rs[r0] + diff != rs[r1]:
                            print "No"
                            exit(0)
        rmin = min(rs.values())
        cmin = min(cs.values())
        if rmin + cmin + base < 0:
            print "No"
            exit(0)
print "Yes"

Submission status: Runtime Error

Solution code:
import z3
print "Yes\n"

Submission status: Runtime Error

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)
V = set()

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.add(("R", r-1))
  V.add(("C", c-1))

def walk(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
      V.remove(w)
      walk(w)

while len(V) > 0:
  col = dict()
  v = V.pop()
  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")