//while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> using namespace std; const int nax=107; const int d=100000; int k; long long n; long long tab[nax]; long long wyn=1; int m; vector <long long> wek, pel; int s1, s2; long long zbi[438766+7]; int ost[d+7]; inline void cons1(const long long &v) { wyn=max(wyn, v); long long lim=n/v; for (int i=0; i<s2 && pel[i]<=lim; i++) wyn=max(wyn, v*pel[i]); } inline void cons2(const long long &v) { long long lim=n/v; if (lim<d) { wyn=max(wyn, v*ost[lim]); return; } int bsa=0; int bsb=m-1; int bss; while(bsa<bsb) { bss=(bsa+bsb+2)>>1; if (zbi[bss]<=lim) bsa=bss; else bsb=bss-1; } wyn=max(wyn, v*zbi[bsa]); } void rek1(int v, long long w) { cons1(w); if (w<=(n/(17*17)) || w==1) { zbi[m]=w; if (w<=d) ost[w]=w; m++; } long long mog=n/w; for (int i=v; i<s1 && wek[i]<=mog; i++) rek1(i, w*wek[i]); } void rek2(int v, long long w) { cons2(w); long long mog=n/w; for (int i=v; i<s2 && pel[i]<=mog; i++) rek2(i, w*pel[i]); } void sortuj(int a, int b) { if (a>=b) return; int s=a+(rand()%(b-a+1)); swap(zbi[s], zbi[b]); int j=a-1; for (int i=a; i<=b; i++) { if (zbi[i]<=zbi[b]) { j++; swap(zbi[i], zbi[j]); } } sortuj(a, j-1); sortuj(j+1, b); } int main(int argc, char *argv[]) { scanf("%d%lld", &k, &n); for (int i=1; i<=k; i++) { scanf("%lld", &tab[i]); if (tab[i]<=13) { wek.push_back(tab[i]); s1++; } else { pel.push_back(tab[i]); s2++; } } sort(wek.begin(), wek.end()); sort(pel.begin(), pel.end()); rek1(0, 1); sortuj(0, m-1); for (int i=1; i<d; i++) if (!ost[i]) ost[i]=ost[i-1]; rek2(0, 1); printf("%lld\n", wyn); 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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | //while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> using namespace std; const int nax=107; const int d=100000; int k; long long n; long long tab[nax]; long long wyn=1; int m; vector <long long> wek, pel; int s1, s2; long long zbi[438766+7]; int ost[d+7]; inline void cons1(const long long &v) { wyn=max(wyn, v); long long lim=n/v; for (int i=0; i<s2 && pel[i]<=lim; i++) wyn=max(wyn, v*pel[i]); } inline void cons2(const long long &v) { long long lim=n/v; if (lim<d) { wyn=max(wyn, v*ost[lim]); return; } int bsa=0; int bsb=m-1; int bss; while(bsa<bsb) { bss=(bsa+bsb+2)>>1; if (zbi[bss]<=lim) bsa=bss; else bsb=bss-1; } wyn=max(wyn, v*zbi[bsa]); } void rek1(int v, long long w) { cons1(w); if (w<=(n/(17*17)) || w==1) { zbi[m]=w; if (w<=d) ost[w]=w; m++; } long long mog=n/w; for (int i=v; i<s1 && wek[i]<=mog; i++) rek1(i, w*wek[i]); } void rek2(int v, long long w) { cons2(w); long long mog=n/w; for (int i=v; i<s2 && pel[i]<=mog; i++) rek2(i, w*pel[i]); } void sortuj(int a, int b) { if (a>=b) return; int s=a+(rand()%(b-a+1)); swap(zbi[s], zbi[b]); int j=a-1; for (int i=a; i<=b; i++) { if (zbi[i]<=zbi[b]) { j++; swap(zbi[i], zbi[j]); } } sortuj(a, j-1); sortuj(j+1, b); } int main(int argc, char *argv[]) { scanf("%d%lld", &k, &n); for (int i=1; i<=k; i++) { scanf("%lld", &tab[i]); if (tab[i]<=13) { wek.push_back(tab[i]); s1++; } else { pel.push_back(tab[i]); s2++; } } sort(wek.begin(), wek.end()); sort(pel.begin(), pel.end()); rek1(0, 1); sortuj(0, m-1); for (int i=1; i<d; i++) if (!ost[i]) ost[i]=ost[i-1]; rek2(0, 1); printf("%lld\n", wyn); return 0; } |