Submission #1127079

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>
#include<functional>
#include<numeric>
#include<sstream>
#include<math.h>
#include <iomanip>
#define ll long long
#define PLL pair<ll,ll>
#define VS vector<string>
#define VL vector<ll>
#define VB vector<bool>
#define VPLL vector<pair<ll,ll> >
#define VVL vector<vector<ll> >
#define VVVL vector<vector<vector<ll> > >
#define VVB vector<vector<bool> >
#define rep(i,a) for (ll i=0;i<a;i++)
#define nrep(i,n,a) for (ll i=n;i<a;i++)
#define mrep(i,a) for(ll i=a;i>=0;i--)
#define INF 1145141919810
#define PI 3.141592653589793238
#define vmin(vec) *std::min_element(vec.begin(),vec.end())
#define vmax(vec) *std::max_element(vec.begin(),vec.end())
#define vsum(vec) std::accumulate(vec.begin(),vec.end(),0LL)
#define ksort(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define ssort(vec) (vec.begin(),vec.end())
#define VPLLsort(vec) sort(vec.begin(), vec.end(),[](PLL &a, PLL &b){ return a.first < b.first; });
#define LTS(n) to_string(n)
#define STL(str) stoll(str)
using namespace std;

ll h, w, mod = 1e9 + 7;
VL dtate{ -1, 0, 1, 0 };
VL dyoko{ 0, 1, 0, -1 };

bool out(ll tate, ll yoko){
	return !(0 <= tate && tate < h && 0 <= yoko && yoko < w);
}

ll dfs(VVL &dp, VVL &a, ll i, ll j){
	if (dp[i][j] != -1) return dp[i][j];
	ll temp;
	temp = 0;
	rep(k, 4) if (!out(i + dtate[k], j + dyoko[k]) && a[i][j]<a[i + dtate[k]][j + dyoko[k]]) temp=temp+dfs(dp,a,i+dtate[k],j+dyoko[k])+1;
	dp[i][j] = temp;
	return dp[i][j];
}
 
int main() {
	cin >> h >> w;
	ll sum=1, temp;
	VVL a(h, VL(w, 0)); rep(i, h) rep(j, w) cin >> a[i][j];
	VVL dp(h, VL(w, -1));
	rep(i, h) rep(j, w){
		sum = (sum + dfs(dp,a, i, j))%mod;
	}cout << (sum + h*w)%mod -1<< endl;
	return 0;
}

Submission Info

Judge Result