#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; vector<int> generate(const vector<int> &p, int limit) { vector<int> result = { 1 }; for(auto x: p) for(int i = 0; i < result.size(); i++) if(1LL * x * result[i] <= limit) result.push_back(x * result[i]); sort(result.begin(), result.end()); return result; } int main() { int n; ll k; scanf("%d %lld", &n, &k); vector<int> va, vb; while(n--) { int p; scanf("%d", &p); if(p < 20) va.push_back(p); else vb.push_back(p); } ll ans = 0; int limit = 10; while(1LL * limit * limit < k) limit *= 10; limit = min((ll)limit, k); for(int i = 0; i < 2; i++) { auto gb = generate(vb, limit); ll st[100] = { 1LL, 0LL }; int m = 1; ans = max(ans, (ll)gb.back()); while(true) { int j = m - 1; if(j < 0) break; if(j == va.size() || st[m] > k / va[j] || st[m] * va[j] > k) m--; else if(st[m] == 0) { st[m] = st[m-1]; st[++m] = 0; } else { st[m] *= va[j]; if(k / st[m] * st[m] <= ans) { m--; continue; } ll t = *(upper_bound(gb.begin(), gb.end(), k / st[m]) - 1); ans = max(ans, st[m] * t); st[++m] = 0; } } va.swap(vb); } printf("%lld\n", ans); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long ll; vector<int> generate(const vector<int> &p, int limit) { vector<int> result = { 1 }; for(auto x: p) for(int i = 0; i < result.size(); i++) if(1LL * x * result[i] <= limit) result.push_back(x * result[i]); sort(result.begin(), result.end()); return result; } int main() { int n; ll k; scanf("%d %lld", &n, &k); vector<int> va, vb; while(n--) { int p; scanf("%d", &p); if(p < 20) va.push_back(p); else vb.push_back(p); } ll ans = 0; int limit = 10; while(1LL * limit * limit < k) limit *= 10; limit = min((ll)limit, k); for(int i = 0; i < 2; i++) { auto gb = generate(vb, limit); ll st[100] = { 1LL, 0LL }; int m = 1; ans = max(ans, (ll)gb.back()); while(true) { int j = m - 1; if(j < 0) break; if(j == va.size() || st[m] > k / va[j] || st[m] * va[j] > k) m--; else if(st[m] == 0) { st[m] = st[m-1]; st[++m] = 0; } else { st[m] *= va[j]; if(k / st[m] * st[m] <= ans) { m--; continue; } ll t = *(upper_bound(gb.begin(), gb.end(), k / st[m]) - 1); ans = max(ans, st[m] * t); st[++m] = 0; } } va.swap(vb); } printf("%lld\n", ans); } |