#include <bits/stdc++.h>
#define trav(a, b) for(auto a : b)
#define mk make_pair
#define f first
#define s second
#define vi vector<int>
#define pb push_back
#define _ << ' ' <<
typedef long long ll;
using namespace std;
const ll modF = 1e9 + 7;
ll ceil(ll a, ll b){
ll res = a / b;
if(a % b != 0)res ++;
return res;
}
int main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n, m, k;
scanf("%lld%lld%lld", &n, &m, &k);
ll a[n][m];
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
scanf("%lld", &a[i][j]);
}
}
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(m, vector<ll>(k + 1)));
int crr = 0;
int prev = 1;
auto val = [&](int i, int j, int it){
if(it == 0)return 0LL;
if(it == 1)return dp[i][j][it];
else return (dp[i][j][it] - dp[i][j][it - 1] + modF) % modF;
};
auto v = [&](int i, int j, int it){
if(it == 0)return 0LL;
return dp[i][j][it];
};
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
dp[crr][j][k] = 0;
for(int it = 1;it < k; it ++){
// cerr << i _ j _ it << '\n';
dp[crr][j][it] = 0;
if(i == 0 and j == 0){
if(a[i][j] == it){
dp[crr][j][it] = 1;
}
} else {
if(it % a[i][j] == 0){
int rem = it / a[i][j];
if(i != 0)dp[crr][j][it] = (dp[crr][j][it] + val(prev, j, rem)) % modF;
if(j != 0)dp[crr][j][it] = (dp[crr][j][it] + val(crr, j - 1, rem)) % modF;
}
}
if(it != 1)
dp[crr][j][it] = (dp[crr][j][it] + dp[crr][j][it - 1]) % modF;
// cerr << dp[crr][j][it] << ' ';
}
// cerr << "yes";
ll req = ceil(k, a[i][j]);
// cerr << req _ a[i][j] << " ";
if(i != 0)
dp[crr][j][k] = (dp[crr][j][k] + (v(prev,j,k) - v(prev,j, req - 1) + modF) % modF) % modF;
if(j != 0)
dp[crr][j][k] = (dp[crr][j][k] + (v(crr,j - 1,k) - v(crr,j - 1, req - 1) + modF) % modF) % modF;
if(k != 1)
dp[crr][j][k] = (dp[crr][j][k] + dp[crr][j][k - 1]) % modF;
// cerr << dp[crr][j][k] << ' ';
}
// cerr << '\n';
crr = 1 - crr;
prev = 1 - prev;
}
ll ans = val(prev,m - 1,k);
printf("%lld\n", ans);
return 0;
}
Compilation message
mobitel.cpp: In function 'int main()':
mobitel.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
22 | scanf("%lld%lld%lld", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf("%lld", &a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
344 ms |
3252 KB |
Output is correct |
| 2 |
Correct |
364 ms |
3436 KB |
Output is correct |
| 3 |
Runtime error |
49 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
47 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
44 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
44 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
45 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
50 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
53 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
53 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
