Submission #774434

---

Source Code Expand

#include<iostream>
#include<queue>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
typedef pair<long long,long long> P;
typedef pair<long long,P> PP;
#define rep2(x,from,to) for(long long (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 10000000
#define K 1000000007
long long h,w;
long long dx[4]={0,0,1,-1};
long long dy[4]={1,-1,0,0};
long long zu[1004][1004];
long long dp[1004][1004];
vector<PP> array;
long long ans;
int main()
{
	cin>>h>>w;
	rep(i,h)
	{
		rep(j,w)
		{
			cin>>zu[i+1][j+1];
			array.push_back(PP(zu[i+1][j+1],P(i+1,j+1)));
		}
	}
	sort(array.begin(),array.end());
	rep(i,w*h)
	{
		P p=array[i].second;
		rep(k,4)
		{
			if(zu[p.first][p.second]<zu[p.first+dx[k]][p.second+dy[k]])
			{
				dp[p.first+dx[k]][p.second+dy[k]]+=(dp[p.first][p.second]+1);
				dp[p.first+dx[k]][p.second+dy[k]]%=K;
			}
		}
	}
	rep(i,1004)rep(j,1004)
	{
		ans+=dp[i][j];
		ans%=K;
	}
	cout<<(ans+w*h)%K<<endl;
	return 0;
}

Submission Info

Judge Result