QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363938#2338. Beautiful BridgesTWTP_TCTFWA 0ms3732kbC++142.0kb2024-03-24 06:12:542024-03-24 06:12:56

Judging History

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

  • [2024-03-24 06:12:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3732kb
  • [2024-03-24 06:12:54]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>


#define ld long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e4 + 2, MOD = 998244353;

int x[N], y[N];


ll dp[N];
ld L[N], R[N];

void doWork() {
    int n, h, a, b;
    cin >> n >> h >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i <= n; i++) {
        L[i] = 1e9;
        int j = i;
        while (j <= n && x[j] <= x[i] + L[i]) {
            int c1 = x[j] - x[i], c2 = y[j] - h;
            ll B = 2 * (c2 - c1), C = 1ll * c1 * c1 + 1ll * c2 * c2;
            ld r = (-B + sqrt(B * B - 4 * C)) / 2;
//            cout<<c1<<" "<<c2<<"\n";
//            cout << B << " " << C << "\n";
//            cout << i << " " << j << " " << r << "\n";
            r = max(r, (ld) h - y[j]);
            L[i] = min(L[i], r);
            j++;
        }
        R[i] = 1e9;
        j = i ;
        while (j && x[j] >= x[i] - R[i]) {
            int c1 = x[j] - x[i], c2 = y[j] - h;
            ll B = 2 * (c1 + c2), C = 1ll * c1 * c1 + 1ll * c2 * c2;
            ld r = (-B + sqrt(B * B - 4 * C)) / 2;
            r = max(r, (ld) h - y[j]);
            R[i] = min(R[i], r);
            j--;
        }
//        cout << L[i] << " " << R[i] << "\n";
    }
    dp[1] = 1ll * (h - y[1]) * a;
    for (int i = 2; i <= n; i++) {
        dp[i] = 1e18;
        for (int j = 1; j < i; j++) {
            if (L[j] + R[i] >= x[i] - x[j]) {
                ll cost = 1ll * (h - y[i]) * a;
                ll d = x[i] - x[j];
                cost += 1ll * d * d * b;
                dp[i] = min(dp[i], dp[j] + cost);
            }
        }
    }
    if (dp[n] < 1e18) {
        cout << dp[n];
    } else {
        cout << "impossible";
    }
}

int main() {

    IO
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

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

output:

1100

result:

ok single line: '1100'

Test #6:

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

input:

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

output:

10010

result:

ok single line: '10010'

Test #7:

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

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

input:

13 43 1 5
3 26
4 25
10 23
11 0
23 2
49 20
64 2
68 0
83 24
84 17
91 33
92 6
97 33

output:

7348

result:

ok single line: '7348'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3652kb

input:

12 29 5 1
4 26
5 18
15 15
27 26
31 12
40 0
46 19
67 4
68 2
77 1
83 12
89 10

output:

1779

result:

wrong answer 1st lines differ - expected: '2134', found: '1779'