1 条题解
-
0

#include <bits/stdc++.h> using std::cin; using std::cout; typedef long long ll; const int N = 254, M = 10054, INF = 0x3f3f3f3f; const ll INF64 = 0x3f3f3f3f3f3f3f3fll; int W; namespace continuous { typedef std::pair <int, int> pr; int n; pr a[N]; double f[M]; inline void push(int b, int k) {a[n++] = pr(b, k);} void solve() { int i, t = 1; double r = 0., ir, start = 0., end, len, taken = 0.; a[n].first = -INF, std::sort(a, a + n, std::greater <pr> ()); for (i = 0; i < n && t <= W; ++i, start = end) { r += 1. / a[i].second, ir = .5 / r, len = (a[i].first - a[i + 1].first) * r; for (end = start + len; t <= end && t <= W; ++t) f[t] = taken + (t - start) * (a[i].first - ir * (t - start)); taken += .5 * len * (a[i].first + a[i + 1].first); } } } namespace discrete { ll f[M], *factory[M], y[M], g[M]; int que[M]; inline void up(ll &x, const ll y) {x < y ? x = y : 0;} inline ll C2(int n) {return n * (n - 1ll) / 2;} inline void init() {memset(f, 192, sizeof f), *f = 0;} inline bool test1(int u, int v, int slope) {return y[u] - y[v] < slope * ll(u - v);} inline bool test2(int u, int v, int w) {return (y[u] - y[v]) * (v - w) <= (y[v] - y[w]) * (u - v);} void dp(int n, ll **f, int V, int dV) { int i, j, h = 0, t = 0; for (i = 0; i < n; ++i) g[i] = *f[i]; for (i = 0; i < n; ++i) { for (; h + 1 < t && test1(que[h + 1], que[h], i * dV); ++h); if (h < t) j = que[h], up(*f[i], g[j] + ll(i - j) * V - C2(i - j) * dV); if (g[i] <= -INF64 / 2) continue; y[i] = i * (i + 1ll) / 2 * dV + i * V - g[i]; for (; h + 1 < t && test2(i, que[t - 1], que[t - 2]); --t); que[t++] = i; } } void push(int w, int V, int dV) { int i, r, c; for (r = 0; r < w; ++r) { for (c = 0, i = r; i <= W; i += w) factory[c++] = f + i; dp(c, factory, V, dV); } } } inline void up(double &x, const double y) {x < y ? x = y : 0;} int main() { int m, u, v, w; double ans = -INFINITY; char ty; std::ios::sync_with_stdio(false), cin.tie(NULL); discrete::init(); for (cin >> m >> W; m; --m) if (cin >> ty, ty == 68) cin >> u >> v >> w, discrete::push(u, v, w); else cin >> u >> v, continuous::push(u, v); if (continuous::n) { continuous::solve(); for (w = 0; w <= W; ++w) if (discrete::f[w] > -INF64 / 2) up(ans, discrete::f[w] + continuous::f[W - w]); cout << std::setprecision(12) << ans << '\n'; } else if (discrete::f[W] <= -INF64 / 2) cout << "impossible\n"; else cout << discrete::f[W] << '\n'; return 0; }
- 1
信息
- ID
- 5738
- 时间
- 3000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者