oj.uz

답안 #501415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501415 2022-01-03T07:28:58 Z zhougz Mobitel (COCI19_mobitel) C++17
130 / 130
 2558 ms 13496 KB 
/**
 *    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

# 결과 실행 시간 메모리 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