QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#551535#2338. Beautiful BridgesRngBased#WA 0ms3716kbC++202.4kb2024-09-07 17:15:362024-09-07 17:15:38

Judging History

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

  • [2024-09-07 17:15:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3716kb
  • [2024-09-07 17:15:36]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;

const ll INF = 1'000'000'000;

pll intersect(pll p, pll q)
{
    return pll(max(p.F, q.F), min(p.S, q.S));
}
pll enough_high(ll yi, ll h)
{
    return pll(h - yi, INF);
}
// solve ax^2 + bx + c <= 0
ll check_root(ll a, ll b, ll c, ll r, int dir)
{
    for (ll i = r - dir * 2; i <= r + dir * 2; i += dir)
        if (a * i * i + b * i + c <= 0)
            return i;
    return dir * INF;
}
pll solve_quadratic(ll a, ll b, ll c)
{
    assert(a >= 0);
    ll D = b * b - 4 * a * c;
    if (D <= 0)
        return pll(INF, -INF);
    double r1 = (-b - sqrt(D)) / (2.0 * a);
    double r2 = (-b + sqrt(D)) / (2.0 * a);
    return pll(check_root(a, b, c, r1, +1),
               check_root(a, b, c, r2, -1));
}
pll under_arch(ll xi, ll x, ll yi, ll h)
{
    return solve_quadratic(1, 4 * (xi - x + yi - h), 4 * (xi - x) * (xi - x) + 4 * (yi - h) * (yi - h));
}

ll n, h, a, b, x[10005], y[10005], dp[10005], in[10005];
vector<int> ord;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> h >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)
        ord.emplace_back(i);
    sort(all(ord), [&](int i, int j) { return y[i] > y[j]; });
    dp[1] = a * (h - y[1]);
    for (int i = 2; i <= n; i++)
    {
        dp[i] = INF * INF;
        pll range = pll(-INF, INF);

        fill(in + 1, in + 1 + n, 0);
        auto increment = [&](int j)
        {
            ++in[j];
            if (in[j] == 2)
            {
                range = intersect(range, enough_high(y[j], h));
                range = intersect(range, under_arch(x[j], x[i], y[j], h));
            }
        };

        int jdx = 0;
        for (int j = i; j >= 1; j--)
        {
            increment(j);
            while (jdx < n && x[i] - x[j] >= 2 * (h - y[ord[jdx]]))
                increment(ord[jdx]), jdx++;

            if (j != i && range.F <= x[i] - x[j] && x[i] - x[j] <= range.S)
                dp[i] = min(dp[i], dp[j] + b * (x[i] - x[j]) * (x[i] - x[j]) + a * (h - y[i]));
        }
    }
    if (dp[n] == INF * INF)
        cout << "impossible\n";
    else 
        cout << dp[n] << '\n';


}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 0ms
memory: 3716kb

input:

2 1 1 1
0 0
2 0

output:

impossible

result:

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