QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532175#2338. Beautiful BridgesSwarthmore#WA 1ms3724kbC++141.3kb2024-08-25 01:02:102024-08-25 01:02:11

Judging History

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

  • [2024-08-25 01:02:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2024-08-25 01:02:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int maxn = 10240;

ll x[maxn], y[maxn];
ll dp[maxn];

int main() {
    int n;
    ll h, alpha, beta;
    cin >> n >> h >> alpha >> beta;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    dp[1] = alpha * (h - y[1]);
    for (int i = 2; i <= n; i++) {
        dp[i] = 1ll << 61;
    }
    for (int i = 2; i <= n; i++) {
        ld lower = 0;
        ld upper = h - y[i];
        for (int j = i-1; j >= 1; j--) {
            ld s = h - y[j];
            ld t = x[i] - x[j];
            ld delta = sqrt(2 * s * t);
            ld ll = s + t - delta;
            ld rr = s + t + delta;
            if (t <= 2 * s) {
                upper = min(upper, rr);
            } else {
                lower = max(lower, ll);
                upper = min(upper, rr);
            }
            ld r = (x[i] - x[j]) / 2.0;
            if (lower - 1e-9 <= r && r <= upper + 1e+9 && r <= h - x[j]) {
                dp[i] = min(dp[i], dp[j] + alpha * (h - y[i]) + beta * (x[i] - x[j]) * (x[i] - x[j]));
            }
        }
    }
    if (dp[n] >= 1ll << 60) {
        cout << "impossible\n";
    } else {
        cout << dp[n] << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

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

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

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

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

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:

impossible

result:

wrong answer 1st lines differ - expected: '7348', found: 'impossible'