Submission #1777598

---

Source Code Expand

#include<iostream>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

int H, W;
ll dp[1000][1000];
ll in[1000][1000];
const int vx[4] = { 0,-1,0,1 };
const int vy[4] = { 1,0,-1,0 };

void reset() {
	for (int i = 0; i < H; i++)for (int j = 0; j < W; j++)dp[i][j] = 0;
}

ll f(int a, int b) {

	if (dp[a][b] != 0)return dp[a][b];

	ll ans = 0;
	for (int i = 0; i < 4; i++) {
		int nx = a + vx[i], ny = b + vy[i];
		if (nx < 0 || ny < 0 || nx >= H || ny >= W)continue;
		if (in[a][b] < in[nx][ny])ans += f(nx, ny) + 1;
	}
	return dp[a][b] = ans;
}

int main() {
	cin >> H >> W;

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> in[i][j];
		}
	}

	ll ans = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {

			reset();

			ans += f(i, j) + 1;
			ans %= MOD;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result