# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
501415 | zhougz | Mobitel (COCI19_mobitel) | C++17 | 2558 ms | 13496 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.
/**
* author: zhougz
* created: 03/01/2022 14:29:45
**/
#include "bits/stdc++.h"
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
const int M = 1'000'000'007;
int r, c, n;
cin >> r >> c >> n;
const int MAXV = 1'000'000;
// Let idx[i] be the max. value C for i : i * C < n
// Strictly less than because we are interested in finding >= which is !<
// We can see for i >= n C is 0. So for our final answer we check @ position 0
// => C = floor((n - 1) / i)
// Problem is we can't span the whole range from 1 to 1 000 000 or there will be no space for dp
// Discretise C first then assign indices
vector<int> v;
for (int i = 1; i <= n; i++) {
v.push_back((n - 1) / i);
}
reverse(v.begin(), v.end());
assert(is_sorted(v.begin(), v.end()));
v.erase(unique(v.begin(), v.end()), v.end());
vector<int> idx(MAXV + 1);
for (int i = 1; i <= n - 1; i++) { // i >= n => (n - 1) / i = 0 = default value
idx[i] = lower_bound(v.begin(), v.end(), (n - 1) / i) - v.begin();
}
vector<vector<int>> arr(r + 1, vector<int>(c + 1));
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> arr[i][j];
}
}
vector<vector<int>> dp(c + 1, vector<int>(v.size())), ndp(c + 1, vector<int>(v.size()));
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (i == 1 && j == 1) {
ndp[j][idx[(n - 1) / arr[1][1]]] = 1;
continue;
}
fill(ndp[j].begin(), ndp[j].end(), 0);
for (auto k : v) { // No choice but to div in case idx overflows
const int good = k / arr[i][j]; // All such numbers when multiplied by arr[i][j] still work
ndp[j][idx[good]] = (ndp[j][idx[good]] + dp[j][idx[k]]) % M;
ndp[j][idx[good]] = (ndp[j][idx[good]] + ndp[j - 1][idx[k]]) % M;
}
}
swap(dp, ndp);
}
// Since first element of v is 0, this is # of ways : even * v[1] (1) is > n
// So only * v[0] (0) is <= n i.e. the elements are already >= n
cout << (dp[c][0] + M) % M;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |