#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int N,M, K;
const long long mod = 1e9+7;
long long mat[500][500];
long long memo[500][500][301];
long long memo2[500][500][301];
bool vis[500][500][301];
long long dp(int i, int j, long long s) {
if (i < 0 ||j<0)return 0;
s*=mat[i][j];
if ( s >= K)return 0;
if (vis[i][j][s])
return memo[i][j][s];
if (i==0 && j==0)return 1;
vis[i][j][s]=true;
return memo[i][j][s] = (dp(i-1,j,s)+dp(i,j-1,s))%mod;
}
long long dp2(int i, int j, long long s) {
if (i < 0 ||j<0)return 0;
if (memo2[i][j][s])
return memo2[i][j][s];
if (i==0 || j==0)return 1;
return memo2[i][j][s] = (dp2(i-1,j,s)+dp2(i,j-1,s))%mod;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >>N>>M>>K;
if (K>300)return 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> mat[i][j];
}
}
cout << (dp2(N-1,M-1,1)-dp(N-1,M-1,1)+mod)%mod;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
86 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
