Submission #100370

#TimeUsernameProblemLanguageResultExecution timeMemory
100370Runtime_error_Mobitel (COCI19_mobitel)C++11
0 / 130
108 ms66560 KiB
#include <bits/stdc++.h> using namespace std; const int inf=3e2+9,mod=1e9+7; int a[inf][inf],n,m,k,dp[inf][inf][inf],Pas[inf+inf][inf+inf]; void build(int n,int m){ Pas[0][0]=1; for(int i=1;i<=n+m;i++) { Pas[i][0]=1; for(int j=1;j<=i;j++) Pas[i][j]=(Pas[i-1][j] + Pas[i-1] [j-1])%mod ; } } int solve(int i,int j,int sum){ if(sum>=k || i>n || j>m) return 0; if(i==n && j==m) return 1; int &ret=dp[i][j][sum]; if(ret!=-1) return ret; ret=0; ret=((long long )ret+solve(i+1,j,sum*a[i+1][j]))%mod; ret=((long long )ret+solve(i,j+1,sum*a[i][j+1]))%mod; return ret; } int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; build(n,m); memset(dp,-1,sizeof(dp)); cout<<(Pas[n+m-2][n-1]-solve(1,1,a[1][1])+mod)%mod<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...