QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389927#2338. Beautiful Bridgesneal2022WA 1ms3620kbC++232.2kb2024-04-14 21:16:402024-04-14 21:16:40

Judging History

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

  • [2024-04-14 21:16:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3620kb
  • [2024-04-14 21:16:40]
  • 提交

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'