Submission #1151123

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int r, c, n;
	cin >> r >> c >> n;
	vector<long long int> sub(100010, mod);
	// sub[i] : i + 1列目 - i列目の値
	map<pair<int, int>, long long int> m;
	vector<vector<int> > rv(100001);
	priority_queue<pair<int, int> > qu;
	for(int i = 0; i < n; i++){
		int rr, cc, a;
		cin >> rr >> cc >> a;
		m[make_pair(rr, cc)] = a;
		qu.push(make_pair(rr, cc));
		rv[rr].push_back(cc);
	}
	while(!qu.empty()){
		int rr = (qu.top()).first;
		int cc = (qu.top()).second;
		// cout << rr << " " << cc << endl;
		if(m[make_pair(rr, cc)] < 0){
			cout << "No" << endl;
			return 0;
		}
		qu.pop();
		if(rr > 1){
			if(m.find(make_pair(rr - 1, cc)) != m.end()){
				// １つ上の値がわかっているとき
				long long int tmp = m[make_pair(rr, cc)] - m[make_pair(rr - 1, cc)];
				if(sub[rr - 1] == mod){
					sub[rr - 1] = tmp;
					for(int i = 0; i < rv[rr].size(); i++){
						qu.push(make_pair(rr, rv[rr][i]));
					}
					for(int i = 0; i < rv[rr - 1].size(); i++){
						qu.push(make_pair(rr - 1, rv[rr - 1][i]));
					}
				} else if(sub[rr - 1] != tmp){
					cout << "No" << endl;
					return 0;
				}
			} else {
				// 1つ上の値がわかっていないとき
				if(sub[rr - 1] != mod){
					// rr行目とrr - 1行目の差がわかっているときは値を設定する
					m[make_pair(rr - 1, cc)] = m[make_pair(rr, cc)] - sub[rr - 1];
					rv[rr - 1].push_back(cc);
					qu.push(make_pair(rr - 1, cc));
				}
			}
		}
		if(rr < r){
			if(m.find(make_pair(rr + 1, cc)) != m.end()){
				// １つ下の値がわかっているとき
				long long int tmp = m[make_pair(rr + 1, cc)] - m[make_pair(rr, cc)];
				if(sub[rr] == mod){
					sub[rr] = tmp;
					for(int i = 0; i < rv[rr].size(); i++){
						qu.push(make_pair(rr, rv[rr][i]));
					}
					for(int i = 0; i < rv[rr + 1].size(); i++){
						qu.push(make_pair(rr + 1, rv[rr + 1][i]));
					}
				} else if(sub[rr] != tmp){
					cout << "No" << endl;
					return 0;
				}
			} else {
				// わかっていないとき
				if(sub[rr] != mod){
					// rr + 1行目とrr行目の差がわかっているときは値を設定する
					m[make_pair(rr + 1, cc)] = sub[rr] + m[make_pair(rr, cc)];
					rv[rr + 1].push_back(cc);
					qu.push(make_pair(rr + 1, cc));
				}
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Submission Info

Judge Result