Submission #1248121

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define pb         push_back

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

ll ma[1005][1005];
ll memo[1005][1005];
int h, w;

ll rec(int y, int x){
	if(memo[y][x] != -1) return memo[y][x];

	ll ret = 1;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny >= 0 && ny < h && nx >= 0 && nx < w && ma[ny][nx] > ma[y][x]){
			ret += rec(ny, nx) % MOD;
			ret %= MOD;
		}
	}

	return memo[y][x] = ret;
}
int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	cin >> h >> w;

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			int a;
			cin >> a;
			ma[i][j] = a;
		}
	}

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			memo[i][j] = -1;
		}
	}

	ll ans = 0;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			//printf("%d ", rec(i, j) + 1);
			ans += (rec(i, j)) % MOD;
			ans %= MOD;
		}
		//puts("");
	}

	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result