Submission #3811737

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;
lint p=1000*1000*1000+7;

int main(){
  int H,W;
  cin>>H>>W;
  vector<array<int,3> > v;
  int a[H][W];
  lint dp[H][W];
  REP(i,H)REP(j,W){
    cin>>a[i][j];
    array<int,3> e={a[i][j],i,j};
    v.push_back(e);
  }
  sort(ALL(v));
  reverse(ALL(v));
  for(auto e:v){
    int h,w;
    h=e[1];w=e[2];
    dp[h][w]=1;
    if(h>0 and a[h-1][w]>a[h][w])dp[h][w]+=dp[h-1][w];
    dp[h][w]%=p;
    if(h<H-1 and a[h+1][w]>a[h][w])dp[h][w]+=dp[h+1][w];
    dp[h][w]%=p;
    if(w>0 and a[h][w-1]>a[h][w])dp[h][w]+=dp[h][w-1];
    dp[h][w]%=p;
    if(w<W-1 and a[h][w+1]>a[h][w])dp[h][w]+=dp[h][w+1];
    dp[h][w]%=p;
  }
  lint ans=0;
  REP(i,H)REP(j,W){
    ans+=dp[i][j];
    ans%=p;  
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result