제출 #1346145

#제출 시각아이디문제언어결과실행 시간메모리
1346145Faisal_SaqibMobitel (COCI19_mobitel)C++20
0 / 130
264 ms131072 KiB
#include <iostream>
#include <map>
using namespace std;
const int N=302,mod=1e9+7;
int a[N][N];
map<int,int> cnt[N][N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r,s,n;
	cin>>r>>s>>n;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=s;j++)
		{
			cin>>a[i][j];
		}
	}
	cnt[1][1][a[1][1]]++;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=s;j++)
		{
			if(i==1 and j==1)continue;
			// merge cnt[i][j-1] and cnt[i-1][j]
			for(auto [w,c]:cnt[i][j-1])
			{
				if(1ll*w*a[i][j]>=n)
				{
					(cnt[i][j][n]+=c)%=mod;
				}
				else
				{
					(cnt[i][j][w*a[i][j]]+=c)%=mod;
				}
			}
			for(auto [w,c]:cnt[i-1][j])
			{
				if(1ll*w*a[i][j]>=n)
				{
					(cnt[i][j][n]+=c)%=mod;
				}
				else
				{
					(cnt[i][j][w*a[i][j]]+=c)%=mod;
				}
			}
		}
	}
	cout<<cnt[r][s][n]<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...