比赛 2022级DP专题练习赛2 评测结果 EEAEWTWWA
题目名称 基站建设 最终得分 22
用户昵称 yrtiop 运行时间 6.409 s
代码语言 C++ 内存使用 11.67 MiB
提交时间 2023-02-13 20:48:34
显示代码纯文本
// Problem: #3825. 「SDOI2012」基站建设
// Contest: LibreOJ
// URL: https://loj.ac/p/3825
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 5e5 + 5;
std::mt19937 rsrsr_bot((unsigned)time(0));
int n;
double x[maxn],r[maxn],v[maxn],s,f[maxn];

int main() {
	freopen("2012sdoi_jzjs.in","r",stdin);
	freopen("2012sdoi_jzjs.out","w",stdout);
	scanf("%d %lf",&n,&s);
	for(int i = 1;i <= n;++ i) {
		scanf("%lf %lf %lf",&x[i],&r[i],&v[i]);
	}
	const int p = rsrsr_bot() % 12392 + 1;
	int t = std::max((int)std::sqrt(n) , p);
	f[1] = v[1];
	for(int i = 2;i <= n;++ i) {
		f[i] = 1e18;
		for(int j = i - 1;j;-- j) {
			f[i] = std::min(f[i] , f[j] + v[i] + (x[i] - x[j]) / 2.0 / std::sqrt(r[j]));
			if(n > 10000&&i - j > t)
				break ;
		}
	}
	double ans = 1e18;
	for(int i = 1;i <= n;++ i) {
		if(r[i] >= x[n] - x[i])
			ans = std::min(ans , f[i]);
	}
	printf("%.3lf\n",ans);
	return 0;
}