比赛 |
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;
}