oj.uz

Submission #200098

# Submission time Handle Problem Language Result Execution time Memory
200098 2020-02-05T10:23:41 Z Saboon Mobitel (COCI19_mobitel) C++14
130 / 130
 4324 ms 11872 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;

int t[300 + 10];
int nex[300 + 10][3000 + 200], dp[300 + 10][3000 + 200], pos[1000000 + 10];

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	k --;
	vector<int> a;
	for (int i = 1; i <= k + 1; i++)
		a.push_back(k / i);
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	for (int i = 0; i < a.size(); i++)
		pos[a[i]] = i;
	int c = a.size();
	dp[0][c - 1] = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++)
			cin >> t[j];
		for (int j = 0; j < m; j++)
			for (int x = 0; x < c; x++)
				nex[j][pos[a[x] / t[j]]] = (nex[j][pos[a[x] / t[j]]] + dp[j][x]) % mod;
		for (int j = 1; j < m; j++)
			for (int x = 0; x < c; x++)
				nex[j][pos[a[x] / t[j]]] = (nex[j][pos[a[x] / t[j]]] + nex[j - 1][x]) % mod;
		for (int j = 0; j < m; j++)
			for (int x = 0; x < c; x++)
				dp[j][x] = nex[j][x], nex[j][x] = 0;
	}
	cout << dp[m - 1][0] << '\n';
}

Compilation message

mobitel.cpp: In function 'int main()':
mobitel.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2936 KB Output is correct
2 Correct 77 ms 2936 KB Output is correct
3 Correct 464 ms 6372 KB Output is correct
4 Correct 502 ms 7028 KB Output is correct
5 Correct 492 ms 7004 KB Output is correct
6 Correct 485 ms 7136 KB Output is correct
7 Correct 251 ms 5856 KB Output is correct
8 Correct 2332 ms 9824 KB Output is correct
9 Correct 4239 ms 11720 KB Output is correct
10 Correct 4324 ms 11872 KB Output is correct