#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<LL> VLL; typedef vector<VI> VVI; typedef pair<int, int> PII; // #define int LL #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define FORE(i, x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i) template <typename T> void _debug(const char *msg, T t) { cerr << msg << "="<< t << "\n"; } template <typename T, typename... R> void _debug(const char *msg, T t, R... r) { while(*msg != ',') cerr << *msg++; cerr << "=" << t << ", "; _debug(msg+1, r...); } #ifdef TEST_ON_LOCAL_MACHINE #define LOCAL #endif #ifdef LOCAL #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__) #define debugv(x) { cerr << #x << " = "; FORE(itt, x) cerr << *itt << ", "; cerr << "\n"; } #else #define debug(...) #define debugv(x) #endif LL solve(LL best, LL current, VI &p, LL last_index, LL n) { debug(best, current, last_index, n); if (n < 1) return best; // // LL final_index = last_index; // while(p[final_index] <= n) // final_index++; // // debug(last_index, final_index); FOR(i, last_index, p.size()-1) { LL x = p[i]; if (n < x) { return max(current, best); } best = max(best, solve(best, current * x, p, i, n / x)); } return best; } int main() { #ifdef TEST_ON_LOCAL_MACHINE freopen("test.in", "r", stdin); #endif LL k, n; scanf("%lld %lld", &k, &n); VI p(k); REP(i, k) scanf("%d", &p[i]); LL best = 1, current = 1; best = solve(best, current, p, 0, n); printf("%lld\n", best); return 0; }
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 69 70 71 72 73 74 75 76 77 78 79 | #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<LL> VLL; typedef vector<VI> VVI; typedef pair<int, int> PII; // #define int LL #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define FORE(i, x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i) template <typename T> void _debug(const char *msg, T t) { cerr << msg << "="<< t << "\n"; } template <typename T, typename... R> void _debug(const char *msg, T t, R... r) { while(*msg != ',') cerr << *msg++; cerr << "=" << t << ", "; _debug(msg+1, r...); } #ifdef TEST_ON_LOCAL_MACHINE #define LOCAL #endif #ifdef LOCAL #define debug(...) _debug(#__VA_ARGS__, __VA_ARGS__) #define debugv(x) { cerr << #x << " = "; FORE(itt, x) cerr << *itt << ", "; cerr << "\n"; } #else #define debug(...) #define debugv(x) #endif LL solve(LL best, LL current, VI &p, LL last_index, LL n) { debug(best, current, last_index, n); if (n < 1) return best; // // LL final_index = last_index; // while(p[final_index] <= n) // final_index++; // // debug(last_index, final_index); FOR(i, last_index, p.size()-1) { LL x = p[i]; if (n < x) { return max(current, best); } best = max(best, solve(best, current * x, p, i, n / x)); } return best; } int main() { #ifdef TEST_ON_LOCAL_MACHINE freopen("test.in", "r", stdin); #endif LL k, n; scanf("%lld %lld", &k, &n); VI p(k); REP(i, k) scanf("%d", &p[i]); LL best = 1, current = 1; best = solve(best, current, p, 0, n); printf("%lld\n", best); return 0; } |