oj.uz

Submission #992381

# Submission time Handle Problem Language Result Execution time Memory
992381 2024-06-04T11:07:03 Z four_specks Building Bridges (CEOI17_building) C++17
100 / 100
 45 ms 8948 KB 
#include <bits/stdc++.h>

using namespace std;

long fl_div(long x, long y) {
  return x / y - ((x ^ y) < 0 && x % y);
}

struct LineContainer {
  struct Line {
    long m, c;
    mutable long p;

    bool operator<(const Line &line) const {
      return m < line.m || (m == line.m && c < line.c);
    }

    bool operator<(long x) const {
      return p < x;
    }
  };

  static constexpr long inf = LONG_MAX;

  using SetType = set<Line, less<>>;

  SetType lines;

  bool isect(SetType::iterator it) {
    if (next(it) == lines.end()) {
      it->p = inf;
      return false;
    }
    if (it->m == next(it)->m) {
      it->p = -inf;
    } else {
      it->p = fl_div(next(it)->c - it->c, it->m - next(it)->m);
    }
    return it->p >= next(it)->p;
  }

  void add(long m, long c) {
    auto it = lines.insert({m, c}).first;
    while (isect(it)) {
      lines.erase(next(it));
    }
    if (it != lines.begin() && isect(--it)) {
      lines.erase(next(it));
      isect(it);
    }
    while (it != lines.begin() && isect(--it)) {
      lines.erase(next(it));
      isect(it);
    }
  }

  long query(long x) {
    auto it = lines.lower_bound(x);
    return it->m * x + it->c;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<long> a(n), b(n);
  for (long &x : a) {
    cin >> x;
  }
  for (long &x : b) {
    cin >> x;
  }
  long ans = 0;
  for (long &x : b) {
    ans += x;
    x = -x;
  }
  LineContainer lc;
  auto add = [&](long m, long c) -> void {
    lc.add(-m, -c);
  };
  auto query = [&](long x) -> long {
    return -lc.query(x);
  };
  add(-2 * a[0], a[0] * a[0] + b[0]);
  for (int i = 1; i < n - 1; i++) {
    long cost = query(a[i]) + a[i] * a[i] + b[i];
    add(-2 * a[i], a[i] * a[i] + cost);
  }
  {
    long cost = query(a[n - 1]) + a[n - 1] * a[n - 1] + b[n - 1];
    ans += cost;
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();

  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2908 KB Output is correct
2 Correct 45 ms 3064 KB Output is correct
3 Correct 37 ms 2908 KB Output is correct
4 Correct 32 ms 2904 KB Output is correct
5 Correct 29 ms 3932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 36 ms 2908 KB Output is correct
7 Correct 45 ms 3064 KB Output is correct
8 Correct 37 ms 2908 KB Output is correct
9 Correct 32 ms 2904 KB Output is correct
10 Correct 29 ms 3932 KB Output is correct
11 Correct 35 ms 3160 KB Output is correct
12 Correct 37 ms 2904 KB Output is correct
13 Correct 27 ms 2916 KB Output is correct
14 Correct 35 ms 3160 KB Output is correct
15 Correct 45 ms 8948 KB Output is correct
16 Correct 31 ms 3924 KB Output is correct
17 Correct 13 ms 2908 KB Output is correct
18 Correct 14 ms 2908 KB Output is correct