QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#389927 | #2338. Beautiful Bridges | neal2022 | WA | 1ms | 3620kb | C++23 | 2.2kb | 2024-04-14 21:16:40 | 2024-04-14 21:16:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 inf = 8e18;
i64 dist2(i64 x1, i64 y1, i64 x2, i64 y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); };
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
i64 n, h, a, b;
std::cin >> n >> h >> a >> b;
auto get_rightmost = [&](std::vector<std::array<int, 2>>& points) {
std::vector<i64> rightmost(n);
for (int i = 0; i < n; i++) {
if (points[i][1] >= h) {
std::cout << "impossible\n";
exit(0);
}
auto check = [&](i64 mid) {
auto r = points[mid][0] - points[i][0];
for (int t = i; t <= mid; t++) {
if (points[t][1] >= h - r &&
dist2(points[t][0], points[t][1], points[mid][0], h - r) > r * r) {
return false;
}
}
return true;
};
i64 l = i, r = n - 1;
while (l < r) {
i64 mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
rightmost[i] = l;
}
return rightmost;
};
std::vector<std::array<int, 2>> points(n);
for (auto& [x, y] : points) std::cin >> x >> y;
auto rightmost = get_rightmost(points);
for (auto& [x, y] : points) x = -x;
std::reverse(points.begin(), points.end());
auto leftmost = get_rightmost(points);
std::reverse(leftmost.begin(), leftmost.end());
for (auto& x : leftmost) x = n - x - 1;
std::reverse(points.begin(), points.end());
for (auto& [x, y] : points) x = -x;
std::vector<i64> dp(n, inf);
dp[0] = a * (h - points[0][1]);
for (int i = 1; i < n; i++) {
// dp[i+1] = cost for building [0, .., i] with pillar at i
for (int j = 0; j < i; j++) {
// cut pillar in [j, .., i]
if (std::min(rightmost[j] - j, i - leftmost[i]) * 2 >= i - j) {
i64 d = points[i][0] - points[j][0];
auto cur = dp[j] + b * d * d + a * (h - points[i][1]);
dp[i] = std::min(dp[i], cur);
}
}
}
if (dp[n - 1] == inf) {
std::cout << "impossible\n";
} else {
std::cout << dp[n - 1] << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 1ms
memory: 3620kb
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: 3580kb
input:
2 1 1 1 0 0 2 0
output:
impossible
result:
wrong answer 1st lines differ - expected: '6', found: 'impossible'