QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576073#2338. Beautiful BridgesneonahtWA 0ms3744kbC++172.7kb2024-09-19 18:15:332024-09-19 18:15:33

Judging History

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

  • [2024-09-19 18:15:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3744kb
  • [2024-09-19 18:15:33]
  • 提交

answer

#include <bits/stdc++.h>
#define DEBUG 0
#define CASES 0
using namespace std;
const int SZ = 1e4 + 7;
const int MX = 1e9 + 7;
const long long MOD = 1e9 + 7;
const long long MXX = 1LL << 62LL;

long long X[SZ], Y[SZ], L[SZ], R[SZ], dp[SZ];
long long n, h, a, b;

bool check(int l, int r) {
    return L[l] >= r && R[r] <= l;
}

bool inRange(int i, int lx, int rx, int mode) {
    if(!mode) return lx <= X[i] && 2*X[i] <= rx + lx && 2*h - rx + lx <= 2*Y[i] && Y[i] <= h;
    return rx + lx <= 2*X[i] && X[i] <= rx && 2*h - rx + lx <= 2*Y[i] && Y[i] <= h;
}

bool inCir(int i, int lx, int rx) {
    long long x=X[i], y=Y[i];
    return 4*x*x + 4*y*y - 4*x*(rx-lx) - 4*y*(2*h-rx+lx) + rx*rx + 2*rx*lx + lx*lx + 4*h*h - 
    4*h*(rx-lx) + rx*rx + 2*rx*lx + lx*lx <= rx*rx - 2*rx*lx + lx*lx;
    // return (2*X[i]-lx-rx)*(2*X[i]-lx-rx) + (2*Y[i]-2*h+rx-lx)*(2*Y[i]-2*h+rx-lx) >= (rx-lx)*(rx-lx);
}

bool good(int l, int r, int mode) {
    if(l >= r) return true;
    long long lx = X[l], rx = X[r];

    for(int i=l; i<=r; i++) {
        if(inRange(i, lx, rx, mode) && !inCir(i, lx, rx)) {
            return false;
        }
    }
    return true;
}

void process(void) {
    cin >> n >> h >> a >> b;

    for(int i=1; i<=n; i++) cin >> X[i] >> Y[i];

    for(int i=1; i<=n; i++) {
        int l=i, r=n+1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(good(i, mid, 0)) {
                L[i] = mid;
                l = mid + 1;
            }
            else r = mid;
        }
    }

    for(int i=1; i<=n; i++) {
        int l=1, r=i+1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(good(i, mid, 1)) {
                R[i] = mid;
                r = mid;
            }
            else l = mid+1;
        }
    }

    if(DEBUG) {
        for(int i=1; i<=n; i++) cout << "L : (" << i << ", " << L[i] << ")" << '\n';
        for(int i=1; i<=n; i++) cout << "R : (" << i << ", " << R[i] << ")" << '\n';
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                cout << good(i, j, 0) << ' ';
            }
            cout << '\n';
        }
    }

    dp[1] = a*(h-Y[1]);

    for(int r=2; r<=n; r++) {
        dp[r] = MXX;
        for(int l=r-1; l>=1; l--) {
            if(check(l, r)) {
                dp[r] = min(dp[r], dp[l] + a*(h-Y[r]) + b*(X[r]-X[l])*(X[r]-X[l]));
            }
        }
    }

    if(dp[n] == MXX) cout << "impossible";
    else cout << dp[n];

    return ;
}

int main() {
    #ifndef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int t(1);
    if(CASES) cin >> t;
    while(t--) process();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3680kb

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: 0ms
memory: 3708kb

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3620kb

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: 0ms
memory: 3736kb

input:

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

output:

8212

result:

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