记录编号	445919	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]货币兑换	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	1.401 s
提交时间	2017-09-07 08:02:50	内存使用	7.16 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100010;

int N;
double A[MAXN], B[MAXN], Rate[MAXN], dp[MAXN];
double Ans, pdec[MAXN];

struct pt {
	double x, y;
	inline bool operator<(pt rhs) const {
		return (x == rhs.x) ? (y < rhs.y) : (x < rhs.x);
	}
	inline pt operator-(pt rhs) { return (pt) { x - rhs.x, y - rhs.y }; }
} P[MAXN], V[MAXN];
inline double cross(pt v, pt w) {
	return v.x * w.y - w.x * v.y;
}
inline double dec(int i, pt p) {
	return A[i] * (p.y + p.x * B[i] / A[i]);
}
void solve(int L, int R) { //[L, R)
	if(R - L == 1) Ans = max(Ans, pdec[L]), dp[L] = (Rate[L] * Ans) / (A[L] * Rate[L] + B[L]);
	else {
		int M = (L + R) / 2;
		solve(L, M);
		//[L, M] --> Convex Hull
		int i, n = 0;
		for(i = L; i < M; i++) V[i] = (pt){dp[i] / Rate[i], dp[i]};
		sort(V + L, V + M);
		for(i = L; i < M; i++) {
			while(n >= 2 && cross(P[n - 1] - P[n - 2], V[i] - P[n - 2]) >= 0) n--;
			P[n++] = V[i];
		}
		//Triary on it
		int k, l, r, m1, m2;
		for(i = M; i < R; i++) {
			l = 0; r = n - 1;
			while(r - l > 3) {
				m1 = l + (r - l) / 3;
				m2 = r - (r - l) / 3;
				if(dec(i, P[m1]) < dec(i, P[m2])) l = m1; else r = m2;
			}
			for(k = l; k <= r; k++) pdec[i] = max(pdec[i], dec(i, P[k]));
		}
		solve(M, R);
	}
}

int main() {
	freopen("cash.in", "rt", stdin);
	freopen("cash.out", "wt", stdout);

	int i, k;
	scanf("%d%lf", &N, &Ans);
	for(i = 1; i <= N; i++) scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);

	solve(1, N + 1);
	printf("%.3lf", Ans);
}