Submission #1151096

---

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 r, c, n;
vector<long long int> sub(100010, mod);
vector<bool> gotsub(100010, false);
map<pair<int, int>, long long int> m;

bool  cansolve(priority_queue<pair<int, int> > qu)
{
	priority_queue<pair<int, int> > newqu, oldqu = qu;
	while(!qu.empty()){
		int rr = (qu.top()).first;
		int cc = (qu.top()).second;
		// cout << rr << " " << cc << endl;
		if(m[make_pair(rr, cc)] < 0){
			return false;
		}
		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(!gotsub[rr - 1]){
					sub[rr - 1] = tmp;
					gotsub[rr - 1] = true;
				} else if(sub[rr - 1] != tmp){
					return false;
				}
			} else {
				// 1つ上の値がわかっていないとき
				if(gotsub[rr - 1]){
					// rr行目とrr - 1行目の差がわかっているときは値を設定する
					m[make_pair(rr - 1, cc)] = m[make_pair(rr, cc)] - sub[rr - 1];
					qu.push(make_pair(rr - 1, cc));
				} else {
					newqu.push(make_pair(rr, 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(!gotsub[rr]){
					sub[rr] = tmp;
					gotsub[rr] = true;
				} else if(sub[rr] != tmp){
					return false;
				}
			} else {
				// わかっていないとき
				if(gotsub[rr]){
					// rr + 1行目とrr行目の差がわかっているときは値を設定する
					m[make_pair(rr + 1, cc)] = sub[rr] + m[make_pair(rr, cc)];
					qu.push(make_pair(rr + 1, cc));
				} else {
					newqu.push(make_pair(rr, cc));
				}
			}
		}
	}
	if(newqu.size() != oldqu.size()) return cansolve(newqu);
	else return true;
}

int main()
{
	cin >> r >> c >> n;
	// sub[i] : i + 1列目 - i列目の値
	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));
	}
	if(cansolve(qu))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Submission Info

Judge Result