Submission #20181763

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

const ll MOD = 1000000007;
int h, w;
ll a[1000][1000];
ll d[1000][1000];

ll dp(int y, int x)
{
  if (d[y][x] >= 0) return d[y][x];

  vector<int> dx { 0, 0,+1,-1};
  vector<int> dy {-1,+1, 0, 0};

  ll r = 1;
  for (int i = 0; i < 4; i++){
    int yy = y + dy[i];
    int xx = x + dx[i];
    if (0 <= yy && yy < h && 0 <= xx && xx < w && a[yy][xx] > a[y][x]){
      r += dp(yy, xx);
      r %= MOD;
    }
  }
  return (d[y][x] = r);
}

int main()
{
  cin >> h >> w;

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

  ll ans = 0;
  for (int y = 0; y < h; y++){
    for (int x = 0; x < w; x++){
      ans += dp(y, x);
      ans %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result