1 条题解

  • 0
    @ 2026-1-12 22:41:13

    #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
    上传者