Submission #501415

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
501415	2022-01-03T07:28:58 Z	zhougz	Mobitel (COCI19_mobitel)	C++17	130 / 130	2558 ms	13496 KB

mobitel

/**
 *    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;
}

Subtask #1

130.0 / 130.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	4800 KB	Output is correct
2	Correct	46 ms	4800 KB	Output is correct
3	Correct	280 ms	9292 KB	Output is correct
4	Correct	306 ms	9892 KB	Output is correct
5	Correct	293 ms	9796 KB	Output is correct
6	Correct	322 ms	9804 KB	Output is correct
7	Correct	155 ms	8916 KB	Output is correct
8	Correct	1414 ms	11880 KB	Output is correct
9	Correct	2477 ms	13324 KB	Output is correct
10	Correct	2558 ms	13496 KB	Output is correct