Submission #2119729

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

const int INF=1000000001;

int main(){
  int H,W;
  cin>>H>>W;
  int a[H+2][W+2];
  vector<pair<int,pair<int,int>>> v(H*W);
  for(int i=0;i<=H+1;i++){
    for(int j=0;j<=W+1;j++){
      if(i==0||i==H+1||j==0||j==W+1){
        a[i][j]=-INF;
      }else{
        cin>>a[i][j];
        v[(i-1)*W+j-1]={a[i][j],{i,j}};
      }
    }
  }
  sort(v.rbegin(),v.rend());
  ll num[H+2][W+2]={};
  for(int i=0;i<H*W;i++){
    int z=v[i].first;
    int r=v[i].second.first;
    int c=v[i].second.second;
    for(int j=-1;j<2;j+=2){
      if(z<a[r+j][c]) (num[r][c]+=num[r+j][c]+1)%=MOD;
      if(z<a[r][c+j]) (num[r][c]+=num[r][c+j]+1)%=MOD;
    }
  }
  ll sum=0;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      //cout<<i<<" "<<j<<" "<<num[i][j]<<endl;
      (sum+=num[i][j]+1)%=MOD;
    }
  }
  cout<<sum<<endl;
  return 0;
}

Submission Info

Judge Result