QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345879 | #2338. Beautiful Bridges | lmf_up | WA | 1ms | 3612kb | C++20 | 1.8kb | 2024-03-07 16:35:55 | 2024-03-07 16:35:56 |
Judging History
answer
#include<bits/stdc++.h>
#define LD double
#define cp const point
#define cl const line
const int maxn=1e4+10;
const LD INF=1e18;
const LD eps=1e-8;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
int X[maxn],Y[maxn];
LD L[maxn],R[maxn];
long long H,A,B;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0),std::cout.tie(0);
int n;
std::cin>>n>>H>>A>>B;
for(int i=1;i<=n;i++)
std::cin>>X[i]>>Y[i];
std::vector<long long>dp(n+1,4e18);
for(int i=1;i<=n;i++)
{
if(i!=n)
{
R[i]=std::min((LD)(X[n]-X[i])/2,(LD)H-Y[i]);
for(int j=i-1;j>=1;j--)
{
if(X[j]-X[i]>R[i])break;
LD t0=Y[j]-H;
LD t2=X[i]-X[j];
LD b=2*(t0+t2),c=t2*t2+t0*t0;
LD r=(-b+sqrtl(b*b-4*c))/2;
R[i]=std::min(R[i],std::min(-t0,r));
}
}
if(i!=1)
{
L[i]=std::min((LD)(X[i]-X[1])/2,(LD)H-Y[i]);
for(int j=i-1;j>=1;j--)
{
if(X[i]-X[j]>L[i])break;
LD t0=Y[j]-H;
LD t2=X[j]-X[i];
LD b=2*(t0+t2),c=t2*t2+t0*t0;
LD r=(-b+sqrtl(b*b-4*c))/2;
L[i]=std::min(L[i],std::min(-t0,r));
}
}
// std::cout<<L[i]<<' '<<R[i]<<std::endl;
}
dp[1]=A*(H-Y[1]);
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
if(R[j]>=(LD)(X[i]-X[j])/2&&L[i]>=(LD)(X[i]-X[j])/2)
dp[i]=std::min(dp[i],dp[j]+A*(H-Y[i])+B*(X[i]-X[j])*(X[i]-X[j]));
}
}
if(dp[n]>=dp[0])
std::cout<<"impossible"<<std::endl;
else std::cout<<dp[n]<<std::endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
5 60 18 2 0 0 20 20 30 10 50 30 70 20
output:
6460
result:
ok single line: '6460'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
4 10 1 1 0 0 1 9 9 9 10 0
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 1 1 1 0 0 2 0
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 1 1 1 0 0 3 0
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
4 5 100 1 0 0 1 3 9 3 10 0
output:
impossible
result:
wrong answer 1st lines differ - expected: '1100', found: 'impossible'