QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#532195#2338. Beautiful BridgesSwarthmore#WA 0ms3792kbC++141.3kb2024-08-25 01:17:542024-08-25 01:17:55

Judging History

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

  • [2024-08-25 01:17:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-08-25 01:17:54]
  • 提交

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 - y[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;
    }
}

详细

Test #1:

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

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

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

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

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

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

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

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'