QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345879#2338. Beautiful Bridgeslmf_upWA 1ms3612kbC++201.8kb2024-03-07 16:35:552024-03-07 16:35:56

Judging History

你现在查看的是最新测评结果

  • [2024-03-07 16:35:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-03-07 16:35:55]
  • 提交

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;

}

Details

Tip: Click on the bar to expand more detailed information

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'