#ifdef _DEBUG #define _GLIBCXX_DEBUG #else # pragma GCC target("avx2") # pragma GCC optimize("O3") # pragma GCC optimize("unroll-loops") #endif #include using namespace std; #include using namespace atcoder; #include #include #include #include using namespace __gnu_pbds; template using gset = tree,rb_tree_tag,tree_order_statistics_node_update>; template using gmap = tree,rb_tree_tag,tree_order_statistics_node_update>; template using ghmap = gp_hash_table; #include using namespace boost; using rat = rational; using mint = modint998244353; // using mint = modint1000000007; // using mint = modint; using ll = int; using lll = __int128_t; using ld = double; using ull = uint64_t; using pll = pair; using vll = vector; using vvll = vector; using vvvll = vector; using vpll = vector; using vvpll = vector; using vm = vector; using vvm = vector; using vvvm = vector; using vstr = vector; #define v(T) vector #define vv(T) vector> #define vvv(T) vector>> #define vvvv(T) vector>>> template istream &operator>>(istream &is, static_modint &a){ll tmp; is >> tmp; a = tmp; return is;} template ostream &operator<<(ostream &os, const static_modint &a){ os << a.val(); return os; } template istream &operator>>(istream &is, dynamic_modint &a){ll tmp; is >> tmp; a = tmp; return is;} template ostream &operator<<(ostream &os, const dynamic_modint &a){ os << a.val(); return os; } string to_string(const __int128_t &a) { if (a == 0) return "0"; string s = ""; __int128_t num = a; bool is_negative = false; if (num < 0) { is_negative = true; num = -num; } while (num > 0) { s += '0' + (num % 10); num /= 10; } if (is_negative) s += '-'; reverse(s.begin(), s.end()); return s; } istream &operator>>(istream &is, __int128_t &a){ string s; is >> s; a = 0; for(char c : s) { if(isdigit(c)) {a = a*10 + (c - '0'); } } if(s[0]=='-'){ a *= -1; } return is; } ostream &operator<<(ostream &os, const __int128_t &a){ os << to_string(a); return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const pair &p) { if(&os == &std::cerr) { os << "(" << p.first << ", " << p.second << ")"; } else { os << p.first << " " << p.second; } return os; } template istream &operator>>(istream &is, vector &vec){ for(T &e : vec){is >> e;} return is; } template ostream &operator<<(ostream &os, const vector &vec) { for(int i = 0; i < (int)vec.size(); i++) { os << vec[i] << (i + 1 != (int)vec.size() ? " " : ""); } return os; } template istream &operator>>(istream &is, deque &vec){ for(T &e : vec){is >> e;} return is; } template ostream &operator<<(ostream &os, const deque &vec) { for(int i = 0; i < (int)vec.size(); i++) { os << vec[i] << (i + 1 != (int)vec.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const set &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; } template ostream &operator<<(ostream &os, const map &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; } template ostream &operator<<(ostream &os, const unordered_map &vec) { for(auto itr = vec.begin(); itr != vec.end(); itr++) { os << (itr != vec.begin() ? " " : "") << (*itr); } return os; } template void read_tuple(istream& is, Tuple& t, index_sequence) { ((is >> std::get(t)), ...); } template istream& operator>>(istream& is, tuple& t) { read_tuple(is, t, index_sequence_for{}); return is; } template void print_tuple(ostream& os, const Tuple& t, index_sequence) { ((os << (Is == 0 ? "" : (&os == &std::cerr ? ", " : " ")) << std::get(t)), ...); } template ostream& operator<<(ostream& os, const tuple& t) { if(&os == &std::cerr) { os << "("; } print_tuple(os, t, index_sequence_for{}); if(&os == &std::cerr) { os << ")"; } return os; } #ifdef _DEBUG template void debug_out(Args... args) { ((std::cerr << " " << args), ...); std::cerr << "\n"; } #define debug(...) do { \ std::cerr << "[" << #__VA_ARGS__ << "]:"; \ debug_out(__VA_ARGS__); \ } while(0) #else #define debug(...) (void)0 #endif template constexpr auto min (T... a) { return min(initializer_list>{a...}); } template constexpr auto max (T... a) { return max(initializer_list>{a...}); } template using pqg = priority_queue, greater>; template T opmin(T x, T y) { return min(x, y); } template T einf() { return numeric_limits::max()/2; } template T opmax(T x, T y) { return max(x, y); } template T eminf() { return numeric_limits::min()/2; } template T opsum(T x, T y) { return x + y; } template T ezero() { return (T)0; } template using minseg = segtree, einf>; template using maxseg = segtree, eminf>; template using sumseg = segtree, ezero>; // template struct v : vector { using vector :: vector; }; // template struct vv : vector> { using vector> :: vector; }; // template struct vvv : vector> { using vector> :: vector; }; template inline bool chmin(T& a, U b) {if(a > b){a = b; return true;} else {return false;}}; template inline bool chmax(T& a, U b) {if(a < b){a = b; return true;} else {return false;}}; template T dist_sq(const pair &x, const pair &y){return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);} template T cross_product(const pair &x, const pair &y){return x.first * y.second - x.second * y.first;} template struct Reverser { T& t; auto begin() const { return std::rbegin(t); } auto end() const { return std::rend(t); } }; template Reverser reversed(T& t) { return {t}; } template Reverser reversed(const T& t) { return {t}; } // #define rep(i,n) for(ll i = 0; i < (ll)(n); i++) #define _GET5(_1,_2,_3,_4,NAME,...) NAME #define _rep1(i, n) for(long long i=0;i<(long long)(n);i++) #define _rep2(i,k,n) for(long long i=(long long)(k);i<(long long)(n);i++) #define _rep3(i,k,n,s) for(long long i=(long long)(k);i<(long long)(n);i+=(s)) #define rep(...) _GET5(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__) #define _rrep1(i, n) for(long long i=(long long)(n) - 1;i>=0;i--) #define _rrep2(i,k,n) for(long long i=(long long)(n)-1;i>=(long long)(k);i--) #define _rrep3(i,k,n,s) for(long long i=(long long)(n);i>=(long long)(k);i-=(s)) #define rrep(...) _GET5(__VA_ARGS__, _rrep3, _rrep2, _rrep1)(__VA_ARGS__) #define repr(i,n) for(ll i = (ll)(n) - 1; i >= 0; i--) #define REP(i, l, r) for(ll i = (ll)l; i <= (ll)(r); i++) #define REPR(i, l, r) for(ll i = (ll)r; i >= (ll)(l); i--) const ll inf = (1 << 30); // const ll INF = (1LL << 60); const vector> DIJ = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; void out(){cout<<'\n';} template void out(const T& a, const Ts&... b){ cout< void outf(const T& a, const Ts&... b){ cout< void outp(pair a){ out((a).first, (a).second); } template void outpf(pair a){ outf((a).first, (a).second); } template void outv(T a){rep(i, (a).size()){ cout << (a)[i] << " "; } cout << endl;} template void outvL(T a){rep(i, (a).size()){out((a)[i]);} cout << flush; } // template void outvv(T a){rep(i, a.size()){ rep(j, a.at(i).size()){cout << a.at(i).at(j) << " "; } cout << endl; }} // template void outvp(T a){rep(i, a.size()){ out2(a.at(i).first, a.at(i).second); }} void setpre(int a){cout << fixed << setprecision(a);} #define outN cout << "No\n" #define outY cout << "Yes\n" void outYN(bool flag) { cout << (flag ? "Yes\n" : "No\n"); } #define dame(...) {outf(__VA_ARGS__);return 0;} template void read(T&... a){(cin >> ... >> a);} #define readll(...) ll __VA_ARGS__; read(__VA_ARGS__) #define readvll(a, n) vector a(n); read(a) #define readvvll(a, n, m) vector> a(n, vector(m)); read(a) #define readvstr(a, n) vector a(n); read(a) #define readvt(type, a, n) vector a(n); read(a) #define readvll2(a, b, n) vector a(n), b(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi] #define readvll3(a, b, c, n) vector a(n), b(n), c(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi] >> (c)[lopi] #define readstr(...) string __VA_ARGS__; read(__VA_ARGS__) #define readundirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1); G[b-1].push_back(a-1);} #define readdirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1);} #define readundirwghG(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1,c); G[b-1].emplace_back(a-1, c);} #define readdirwghG(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1, c);} #define All(a) (a).begin(), (a).end() #define all(a) begin(a), end(a) template inline void sortr(T& a){ sort((a).rbegin(), (a).rend()); } template inline vector argsort(T V, bool rev = false){vector res(V.size()); iota(res.begin(), res.end(), 0); sort(res.begin(), res.end(), [&](int x, int y){if(!rev){return V[x] < V[y];}else{return V[x] > V[y];}}); return res;} template inline void sort_by_idx(T& V, vector& I){assert(V.size() == I.size()); T tmpv = V; for(int loopi = 0; loopi < (int)I.size(); loopi++){V[loopi] = tmpv[I.at(loopi)];}} template inline void sortp(vector& v1, vector& v2, bool rev1 = false, int rev2 = false){assert(v1.size() == v2.size()); vector I(v1.size()); iota(I.begin(), I.end(), 0); sort(I.begin(), I.end(), [&](const int x, const int y){if(v1[x] != v1[y]){return (bool)(rev1 ^ (v1[x] < v1[y]));}else{if(v2[x]==v2[y]){return false;} return (bool)(rev2 ^ (v2[x] < v2[y]));}}); sort_by_idx(v1, I); sort_by_idx(v2, I);} template T POW(T x, ll n) {T ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;} ll powll(ll x, ll n){ll ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;} ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;} ll sqrtll(ll a){assert(a >= 0); ll r = (ll)sqrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1) <= a) r++; return r;} ll cbrtll(ll a){assert(a >= 0); ll r = (ll)cbrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1)*(r+1) <= a) r++; return r;} ll modinv(ll a, ll b){assert(a); if(a == 1) return 1; if(b == 1) return 0; ll ret = (1ll-b*modinv(b%a, a))/a; ret %= b; if(ret < 0) ret += b; return ret;} inline ll divceil(ll x, ll y) { if(x >= 0) {return(x / y + (ll)(x % y != 0)); } else { return -((-x) / y); } } inline ll divfloor(ll x, ll y) { if(x >= 0) { return x/y; } else { return -((-x)/y + (ll)((-x) % y != 0)); } } inline bool inLR(ll x, ll L, ll R){ return (L <= x && x < R); } inline bool inRect(ll pos_x, ll pos_y, ll rect_H, ll rect_W, ll rect_h = 0, ll rect_w = 0){ return (rect_h <= pos_x && pos_x < rect_H && rect_w <= pos_y && pos_y < rect_W); } template vector &operator++(vector& v){for(T& x : v) x++; return v;} template vector &operator--(vector& v){for(T& x : v) x--; return v;} template vector operator++(vector& v, signed){auto res = v; for(T& x : v) x++; return res;} template vector operator--(vector& v, signed){auto res = v; for(T& x : v) x--; return res;} template vector operator+=(vector& v, const vector& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] += w[i]; return v;} template vector operator-=(vector& v, const vector& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] -= w[i]; return v;} template vector operator*=(vector& v, const vector& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] *= w[i]; return v;} template vector operator/=(vector& v, const vector& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] /= w[i]; return v;} template vector operator+(vector v, const vector& w){return (v += w);} template vector operator-(vector v, const vector& w){return (v -= w);} template vector operator*(vector v, const vector& w){return (v *= w);} template vector operator/(vector v, const vector& w){return (v /= w);} template vector operator*=(vector& v, T w){for(T& x : v) x*=w; return v;} template vector operator/=(vector& v, T w){for(T& x : v) x/=w; return v;} template vector operator*(vector v, T x){return (v *= x);} template vector operator/(vector v, T x){return (v /= x);} template pair operator+=(pair& p, const pair& q){p.fi+=q.fi, p.se+=q.se; return p;} template pair operator+(pair p, const pair& q){return (p += q);} template pair operator-=(pair& p, const pair& q){p.fi-=q.fi, p.se-=q.se; return p;} template pair operator-(pair p, const pair& q){return (p -= q);} template size_t HashCombine(const size_t seed,const T &v){ return seed^(std::hash()(v)+0x9e3779b9+(seed<<6)+(seed>>2)); } template struct std::hash>{ size_t operator()(const std::pair &keyval) const noexcept { return HashCombine(std::hash()(keyval.first), keyval.second); } }; template struct std::hash>{ size_t operator()(const std::vector &keyval) const noexcept { size_t s=0; for (auto&& v: keyval) s=HashCombine(s,v); return s; } }; template struct HashTupleCore{ template size_t operator()(const Tuple &keyval) const noexcept{ size_t s=HashTupleCore()(keyval); return HashCombine(s,std::get(keyval)); } }; template <> struct HashTupleCore<0>{ template size_t operator()(const Tuple &keyval) const noexcept{ return 0; } }; template struct std::hash>{ size_t operator()(const tuple &keyval) const noexcept { return HashTupleCore>::value>()(keyval); } }; // vll Dijkstra(const vector> &g, ll st = 0) {ll N = g.size(); pqg pq; vll dist(N, INF); pq.emplace(0, st); dist[st] = 0; while(!pq.empty()) { auto [d, n] = pq.top(); pq.pop(); if(dist[n] < d){continue;} for(auto [e, c] : g[n]) { if(chmin(dist[e], dist[n] + c)) { pq.emplace(dist[e], e); } } } return dist; } using vr = vector; using vvr = vector; using vld = vector; using vvld = vector; class Timer { using tp = chrono::_V2::system_clock::time_point; private: tp start_time; unordered_map memo_time; unordered_map memo_bf; int64_t sum_until, count_until; tp bf_until; int64_t sum_auntil, count_auntil; tp bf_auntil; public: Timer() {} ~Timer() {} inline tp now() { return chrono::system_clock::now(); } inline int64_t diff(tp to) { return chrono::duration_cast(to-start_time).count(); } // dif [microsec] inline int64_t diff(tp from, tp to) { return chrono::duration_cast(to-from).count(); } void init() { start_time = now(); sum_until = 0; count_until = 0; sum_auntil = 0; count_auntil = 0; } void start(string key) { memo_bf[key] = now(); } void stop(string key) { memo_time[key] += diff(memo_bf[key], now()); } bool until(int64_t fin_time, double buf_time = 1.5, bool show_count = false) { tp now_time = now(); if(count_until == 0) { sum_until = 0; } else { sum_until += diff(bf_until, now_time); } bf_until = now_time; count_until++; if((fin_time*1000) - diff(start_time, now_time) > buf_time * sum_until / (count_until == 1 ? 1 : count_until - 1)) { return true; } else { if(show_count) { cout << "# count_until : " << count_until - 1 << "\n"; } count_until = 0; return false; } } bool until_annealing(int64_t fin_time, long double &temperature, long double c, double buf_time = 1.5, bool show_debug = false) { tp now_time = now(); if(count_auntil == 0) { sum_auntil = 0; } else { sum_auntil += diff(bf_auntil, now_time); } bf_auntil = now_time; count_auntil++; temperature *= c; if((fin_time*1000) - diff(start_time, now_time) > buf_time * sum_auntil / (count_auntil == 1 ? 1 : count_auntil - 1)) { return true; } else { if(show_debug) { cout << "# count_until : " << count_auntil - 1 << "\n"; cout << "# temperature : " << temperature << "\n"; } count_auntil = 0; return false; } } void show_timers() { cout << "# timers [ms]\n"; int64_t sm = 0; for(auto &[key, val] : memo_time) { cout << "# " << key << " :" << val / 1000.0 << "\n"; sm += val; } cout << "# res :" << (diff(start_time, now()) - sm)/1000.0 << "\n"; cout << "#############\n"; } }; mt19937 mt(998244353); int main() { std::cin.tie(nullptr), std::ios_base::sync_with_stdio(false); Timer timer; timer.init(); auto st = timer.now(); readll(N, X, Y); readvll3(W, V, C, N); // rat ok = 0; // rat ng = 0; ld ok = 0; ld ng = 0; ll dR[500*600 + 1]; ld dT[500*600 + 1]; rep(i, 500*600 + 1) { dR[i] = i%X; dT[i] = i/X; } rep(i, N) ng += V[i]*C[i] + (W[i]*C[i]+X-1)/X*Y + 1; while(ng - ok >= 1e-6 || (ng - ok)/(ok + ng) >= 1e-6) { if(timer.diff(st, timer.now()) >= 1940000) break; ld k = (ok + ng)/2; vld dp(X, -inf); bool fin = false; rep(i, N) { vld ndp(X, -inf); { rep(x, 1, C[i] + 1) { ll nr = dR[(W[i]*x)]; ld nval = (V[i] - k*W[i])*x + dT[(W[i]*x)]*Y; chmax(ndp[nr], nval); if(nval >= 0) { fin = true; break; } } } rep(x, C[i] + 1) { if(fin) break; rep(r, X) { ll nr = dR[(r + W[i]*x)]; ld nval = dp[r] + (V[i] - k*W[i])*x + dT[(r+W[i]*x)]*Y; chmax(ndp[nr], nval); if(nval >= 0) { fin = true; break; } } } if(fin) break; ndp.swap(dp); } // debug(k); // debug(dp); // ld mx = *max_element(all(dp)); if(fin) ok = k; else ng = k; } setpre(20); // out((ld)ok.numerator()/ok.denominator()); out(uniform_real_distribution(ok, ng)(mt)); // cerr << ng - ok << endl; }