QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266007#2338. Beautiful BridgesInfinityNS#WA 1ms3984kbC++142.2kb2023-11-26 00:41:272023-11-26 00:41:28

Judging History

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

  • [2023-11-26 00:41:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3984kb
  • [2023-11-26 00:41:27]
  • 提交

answer

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
using namespace std;

const ll oo=LLONG_MAX/2;
vector<pair<int,int>> sols(int x,int y){
    ll k=2*(ll)x*y;
    double a=sqrtl(k);
    ll sq=-1;
    for(ll x=a-2;x<=a+2;x++){
        if(x*x==k){
            sq=x;
        }
    }
    int badL=-1,badR=-1;
    if(sq!=-1){
        badL=2*(x+y-sq)-1;
        badR=2*(x+y+sq)+1;
    }
    else{
        badL=floor(2*(x+y-a));
        badR=ceil(2*(x+y+a));
    }
    badL=max(badL,0);
    y=y*2;
    y=max(y,x-1);
    if(badL>y){
        return {{y+1,badL},{badR,INT_MAX}};
    }
    else{
        if(badR>y){
            return {{badR,INT_MAX}};
        }
        else{
            return {{y+1,INT_MAX}};
        }
    }
}
int main(){
    int n,h,a,b;
    cin>>n>>h>>a>>b;
    vector<ll> dp(n,oo);
    vector<int> x(n),y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
        y[i]=h-y[i];
    }
    const int N=1e5+5;
    vector<int> next(N,INT_MAX);
    for(int i=0;i<n;i++){
        next[x[i]]=i;
    }
    for(int i=N-2;i>=0;i--){
        next[i]=min(next[i],next[i+1]);
    }
    dp[n-1]=(ll)a*y[n-1];
    vector<int> c(n);
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++)x[j]-=x[i],c[j]=0;
        int cntBad=0;
        for(int j=i+1;j<n;j++){
            /*cout << i << " " << j << endl;
            for(auto p:sols(x[j],y[j])){
                cout << "bad " << p.f << " " << p.s << endl;
            }*/
            for(auto p:sols(x[j],y[j])){
                p.f+=x[i];
                if(p.s!=INT_MAX)
                    p.s+=x[i]+1;
                if(next[p.f]!=INT_MAX){
                    c[next[p.f]]++;
                }
                if(p.s!=INT_MAX&&next[p.s]!=INT_MAX){
                    c[next[p.f]]--;
                }
            }
            cntBad+=c[j];
            if(cntBad==0){
                dp[i]=min(dp[i],dp[j]+(ll)x[j]*x[j]*b+(ll)y[i]*a);
            }
        }



        for(int j=i+1;j<n;j++)x[j]+=x[i];
    }
    if(dp[0]>=oo){
        printf("impossible\n");
    }
    else
        printf("%lld\n",dp[0]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3984kb

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: 3732kb

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: 1ms
memory: 3792kb

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

4 5 100 1
0 0
1 3
9 3
10 0

output:

1100

result:

ok single line: '1100'

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3660kb

input:

4 5 1 100
0 0
1 3
9 3
10 0

output:

6614

result:

wrong answer 1st lines differ - expected: '10010', found: '6614'