# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
334953 | ronnith | Mobitel (COCI19_mobitel) | C++14 | 63 ms | 65540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(n, vector<vector<ll>>(m, vector<ll>(k + 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 ++){
for(int it = 1;it < k; it ++){
// cerr << i _ j _ it << '\n';
dp[i][j][it] = 0;
if(i == 0 and j == 0){
if(a[i][j] == it){
dp[i][j][it] = 1;
}
} else {
if(it % a[i][j] == 0){
int rem = it / a[i][j];
if(i != 0)dp[i][j][it] = (dp[i][j][it] + val(i - 1, j, rem)) % modF;
if(j != 0)dp[i][j][it] = (dp[i][j][it] + val(i, j - 1, rem)) % modF;
}
}
if(it != 1)
dp[i][j][it] = (dp[i][j][it] + dp[i][j][it - 1]) % modF;
}
// cerr << "yes";
ll req = ceil(k, a[i][j]);
// cerr << req _ a[i][j];
if(i != 0)
dp[i][j][k] = (dp[i][j][k] + (v(i - 1,j,k) - v(i - 1,j, req - 1) + modF) % modF) % modF;
if(j != 0)
dp[i][j][k] = (dp[i][j][k] + (v(i,j - 1,k) - v(i,j - 1, req - 1) + modF) % modF) % modF;
if(k != 1)
dp[i][j][k] = (dp[i][j][k] + dp[i][j][k - 1]) % modF;
}
}
ll ans = val(n - 1,m - 1,k);
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |