Submission #159815

#TimeUsernameProblemLanguageResultExecution timeMemory
159815theknife2001Mobitel (COCI19_mobitel)C++17
0 / 130
70 ms65540 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=355; const int mod=1e9+7; int dp[N][N][N]; int a[N][N]; int n,m,M; int 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; int &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; }
#Verdict Execution timeMemoryGrader output
Fetching results...