QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#551535 | #2338. Beautiful Bridges | RngBased# | WA | 0ms | 3716kb | C++20 | 2.4kb | 2024-09-07 17:15:36 | 2024-09-07 17:15:38 |
Judging History
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'