【雅礼联考DAY01】逃跑

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include<cstdio>

using namespace std;

const int N = 30000;

const double INF = 1e8;

int n , l , a[N + 5] , b[N + 5] , c[N + 5] , q[N + 5] , head , tail , Mk , Mc;

double ans , f[N + 5] , w[N + 5];

struct tree{double max , tag;}t[(N << 2) + 5];

inline double max(double x , double y) {return x > y ? x : y;}

inline void build(int l , int r , int k)

{

	t[k] = (tree){0 , 0};

	if (l == r)

	{

		t[k].max = f[l];

		return;

	}

	int mid = (l + r) >> 1;

	if (l <= mid) build(l , mid , k << 1);

	if (r > mid) build(mid + 1 , r , k << 1 | 1);

	t[k].max = max(t[k << 1].max , t[k << 1 | 1].max);

}

inline void pushdown(int k)

{

	if (!t[k].tag) return;

	t[k << 1].max += t[k].tag;

	t[k << 1 | 1].max += t[k].tag;

	t[k << 1].tag += t[k].tag;

	t[k << 1 | 1].tag += t[k].tag;

	t[k].tag = 0;

}

inline void update(int l , int r , int k , int x , double v)

{

	if (l == r && l == x)

	{

		t[k].max = v;

		return;

	}

	int mid = (l + r) >> 1;

	pushdown(k);

	if (x <= mid) update(l , mid , k << 1 , x , v);

	if (x > mid) update(mid + 1 , r , k << 1 | 1 , x , v);

	t[k].max = max(t[k << 1].max , t[k << 1 | 1].max);

}

inline void change(int l , int r , int k , int tl , int tr , double v)

{

	if (l >= tl && r <= tr)

	{

		t[k].tag += v;

		t[k].max += v;

		return;

	}

	int mid = (l + r) >> 1;

	pushdown(k);

	if (tl <= mid) change(l , mid , k << 1 , tl , tr , v);

	if (tr > mid) change(mid + 1 , r , k << 1 | 1 , tl , tr , v);

	t[k].max = max(t[k << 1].max , t[k << 1 | 1].max);

}

inline double query(int l , int r , int k , int tl , int tr)

{

	if (l >= tl && r <= tr) return t[k].max;

	int mid = (l + r) >> 1;

	double res = -INF;

	pushdown(k);

	if (tl <= mid) res = max(res , query(l , mid , k << 1 , tl , tr));

	if (tr > mid) res = max(res , query(mid + 1 , r , k << 1 | 1 , tl , tr));

	return res;

}

inline bool check(double m)

{

	for(register int i = 1; i <= n; i++) w[i] = a[i] - b[i] * m , f[i] = -INF;

	f[0] = 0;

	build(0 , n , 1);

	q[head = tail = 1] = 0;

	for(register int i = 1; i <= n; i++)

	{

		while (head < tail && c[i] >= c[q[tail]])

		{

			change(0 , n , 1 , q[tail - 1] , q[tail] - 1 , -w[q[tail]]);

			tail--;

		}

		q[++tail] = i;

		change(0 , n , 1 , q[tail - 1] , q[tail] - 1 , w[q[tail]]);

		f[i] = query(0 , n , 1 , i - l > 0 ? i - l : 0 , i - 1);

		update(0 , n , 1 , i , f[i]);

	}

	return f[n] >= 0;

}

int main()

{

//	freopen("逃跑.in" , "r" , stdin);

	scanf("%d%d" , &n , &l);

	for(register int i = 1; i <= n; i++) scanf("%d%d%d" , &a[i] , &b[i] , &c[i]);

	c[0] = INF;

	double l = 0 , r = 1e6 , mid;

	for(register int i = 1; i <= 60; i++)

	{

		mid = (l + r) * 0.5;

		if (check(mid)) l = mid , ans = mid;

		else r = mid;

	}

	if (ans == 0)

	{

		puts("0.000000000e+000");

		return 0;

	}

	Mk = 0 , Mc;

	if (ans < 1)

	{

		while (ans < 1) ans *= 10 , Mk++;

		printf("%.9lfe-" , ans);

		if (Mk == 0) Mc = 3;

		else if (Mk < 10) Mc = 2;

		else if (Mk < 100) Mc = 1;

		else Mc = 0;

		while (Mc--) putchar('0');

		if (Mk > 0) printf("%d" , Mk);

		return 0;

	}

	while (ans >= 10) ans /= 10 , Mk++;

	printf("%.9lfe+" , ans);

	if (Mk == 0) Mc = 3;

	else if (Mk < 10) Mc = 2;

	else if (Mk < 100) Mc = 1;

	else Mc = 0;

	while (Mc--) putchar('0');

	if (Mk > 0) printf("%d" , Mk);

}
巴特西

【雅礼联考DAY01】逃跑

最新文章

热门文章
