题意
题目链接
Sol
解题的关键是看到题目里的提示。。。
设(f[i])表示到第(i)天所持有软妹币的最大数量，显然答案为(max_{i = 1}^n f[i])
转移为(f_i = max(f_{i - 1}, A_i frac{f_j R_j}{A_j R_j B_j} B_i frac{f_j}{A_j R_j B_j}))
设(y_i = frac{f_j}{A_j R_j B_j}, x_i = frac{f_j R_j}{A_j R_j B_j})
显然可以斜率优化，也就是拿一条斜率为(frac{A_i}{B_i})的直线从上往下切。
但是这里的斜率和(x)都是不单调的。
按照老祖宗说的
(x)不单调cdq
斜率不单调二分凸包
然后xjb写一写就好了。我写的cdq复杂度是(O(nlog^2n))的，每次暴力建左侧的凸包，然后在右边二分，虽然很好写，但是在BZOJ上成功T飞。。
看了下SovietPower大佬的博客发现有nlogn的做法Orz，就是先按斜率排序，然后转移的时候把下标分为(<mid)和(>= mid)的，直接用类似双指针的东西扫就行了
代码语言：javascript复制#include<bits/stdc .h>
#define Pair pair<double, double>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long
#define LL long long
#define db double
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 10, mod = 1e9 7, INF = 1e9 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x y < 0) return x y mod; return x y >= mod ? x y - mod : x y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x y < 0) x = x y mod; else x = (x y >= mod ? x y - mod : x y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod mod) % mod;}
template <typename A> inline void debug(A a){cout << a << 'n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, S;
struct Sta {
int id;
db A, B, R, x, y, f;
void Get() {
x = f * R / (A * R B);
y = f / (A * R B);
}
bool operator < (const Sta &rhs) const {
return f < rhs.f;
}
}a[MAXN], st[MAXN];
vector<Pair> v;
double GetK(Pair a, Pair b) {
if((b.fi - a.fi) < eps) return INF;
return (b.se - a.se) / (b.fi - a.fi);
}
void GetConvexHull(int l, int r) {
v.clear();
for(int i = l; i <= r; i ) {
double x = a[i].x, y = a[i].y;
while(v.size() > 1 && ((GetK(v[v.size() - 1], MP(x, y)) > GetK(v[v.size() - 2], v[v.size() - 1])) )) v.pop_back();
v.push_back(MP(x, y));
}
}
int cnt = 0;
db Find(int id, db k) {
int l = 0, r = v.size() - 1, ans = 0;
while(l <= r) {
int mid = l r >> 1;
if((mid == 0) || (GetK(v[mid - 1], v[mid]) > k)) l = mid 1, ans = mid;
else r = mid - 1;
}
return a[id].A * v[ans].fi a[id].B * v[ans].se;
}
db CDQ(int l, int r) {
if(l == r) {
int i = l;
chmax(a[i].f, a[i - 1].f);
chmax(a[i].f, a[i].f * ((a[i].A * a[i].R a[i].B) / (a[i].A * a[i].R a[i].B)));
a[l].Get();
return a[i].f;
}
int mid = l r >> 1;
db lmx = CDQ(l, mid);
GetConvexHull(l, mid);
for(int i = mid 1; i <= r; i ) chmax(a[i].f, max(lmx, Find(i, -a[i].A / a[i].B)));
CDQ(mid 1, r);
int tl = l, tr = mid 1, tot = tl - 1;
while(tl <= mid || tr <= r) {
if((tr > r) || (tl <= mid && a[tl].x < a[tr].x)) st[ tot] = a[tl ];//这里要加上tl <= mid
else st[ tot] = a[tr ];
}
db rt = 0;
for(int i = l; i <= r; i ) a[i] = st[i], chmax(rt, a[i].f);
return rt;
}
signed main() {
// freopen("a.in", "r", stdin);
N = read(); S = read();
for(int i = 1; i <= N; i ) scanf("%lf %lf %lf", &a[i].A, &a[i].B, &a[i].R), a[i].id = i;
a[0].f = S;
CDQ(1, N);
db ans = 0;
for(int i = 1; i <= N; i ) chmax(ans, a[i].f);
printf("%.3lf", ans);
return 0;
}
