Submission #159814

#	Time	Username	Problem	Language	Result	Execution time	Memory
159814		theknife2001	Mobitel (COCI19_mobitel)	C++17	0 / 130	65 ms	65540 KiB

mobitel

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=355;
const int mod=1e9+7;
ll dp[N][N][N];
ll a[N][N];
int n,m,M;
ll bt(int i , int j, ll val)
{
	if(i==n-1&&j==m-1)
	{
		if(val*a[i][j]>=M)
		return 1LL;
		return 0LL;
	}
	if(val>M)
	val=M;
	ll &ret=dp[i][j][val];
	if(ret!=-1)
	return ret;
	ret=0;
	if(i+1<n)
	ret+=bt(i+1,j,val*a[i][j]);
	if(j+1<m)
	ret+=bt(i,j+1,val*a[i][j]);
	ret%=mod;
	return ret;
}

int main()
{
	memset(dp,-1,sizeof dp);
	ios::sync_with_stdio(false);
	cin>>n>>m>>M;
	if(M>300)
	assert(0);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	}
	cout<<bt(0,0,1)<<endl;
	
	
	
	return 0;
}

• Subtask 1: 0 / 130