Submission #2546108

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};

int main() {
  int H, W;
  while (cin >> H >> W) {
    vector<vector<int>> a(H, vector<int>(W));
    for (int y = 0; y < H; y++) {
      for (int x = 0; x < W; x++) {
        cin >> a[y][x];
      }
    }
    vector<vector<ll>> dp(H, vector<ll>(W, -1));
    function<ll(int, int)> solve = [&](int y, int x) {
      ll &res = dp[y][x];
      if (res != -1) return res;
      res = 1;
      for (int i = 0; i < 4; i++) {
        int ny = y + dy[i], nx = x + dx[i];
        if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
        if (a[ny][nx] <= a[y][x]) continue;
        res = (res + solve(ny, nx)) % MOD;
      }
      return res;
    };
    ll res = 0;
    for (int y = 0; y < H; y++) {
      for (int x = 0; x < W; x++) {
        res = (res + solve(y, x)) % MOD;
      }
    }
    cout << res << endl;
  }
  return 0;
}

Submission Info

Judge Result