oj.uz

Submission #1109487

# Submission time Handle Problem Language Result Execution time Memory
1109487 2024-11-06T21:36:39 Z available3124 Building Bridges (CEOI17_building) C++14
100 / 100
 83 ms 11348 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define int long long

const int maxn = 2e5;

struct convex_trick {
  struct Line {
    bool type;
    double x;
    int k, b;

    const bool operator<(const Line &other) const {
      if (type || other.type) {
        return x < other.x;
      }
      return k > other.k;
    }
  };


  double intersection(const set<Line>::iterator &l, const set<Line>::iterator &r) { return (double)(l->b - r->b) / (r->k - l->k); }

  set<Line> lines;

  inline bool has_prev(const set<Line>::iterator &it) { return it != lines.begin(); }
  inline bool has_next(const set<Line>::iterator &it) { return it != lines.end() && next(it) != lines.end(); }


  bool bad(set<Line>::iterator it) {
    if (has_next(it) && next(it)->b <= it->b) return true;
    return (has_prev(it) && has_next(it) && intersection(prev(it), next(it)) <= intersection(prev(it), it));
  }

  void calc_x(const set<Line>::iterator &it) {
    if (has_prev(it)) {
      Line l = *it;
      l.x = intersection(prev(it), it);
      lines.insert(lines.erase(it), l);
    }
  }

  void add_line(int k, int b) {
    set<Line>::iterator it;

    it = lines.lower_bound({0, 0, k, b});
    if (it != lines.end() && it->k == k) {
      if (it->b <= b) return;
      lines.erase(it);
    }
    it = lines.insert({0, 0, k, b}).first;
    if (bad(it)) {
      lines.erase(it);
    } else {
      while (has_prev(it) && bad(prev(it))) lines.erase(prev(it));
      while (has_next(it) && bad(next(it))) lines.erase(next(it));

      if (has_next(it)) calc_x(next(it));
      calc_x(it);
    }
  }

  int query(int x) {
    if (!has_prev(lines.upper_bound({1, (double)x, 0, 0}))) {
      assert(false);
    }
    Line l = *prev(lines.upper_bound({1, (double)x, 0, 0}));
    return l.k * x + l.b;
  }
};

struct Rect {
  int w, h;
  const bool operator<(const Rect &other) const {
    return w < other.w || (w == other.w && h > other.h);
  }
};

void run_test(int test_case) {
  int n;
  cin >> n;
  vector<int> h(n + 1), w(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    tot += w[i];
  }
  vector<int> dp(n + 1);
  dp[1] = -w[1];
  convex_trick cht;
  for (int i = 2; i <= n; i++) {
    cht.add_line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
    dp[i] = cht.query(h[i]) - w[i] + h[i] * h[i];
  }
  cout << tot + dp[n] << '\n';
}

signed main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int test_cases = 1;
  // cin >> test_cases;

  for (int i = 1; i <= test_cases; i++) {
    run_test(i);
  }

  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2896 KB Output is correct
2 Correct 58 ms 2880 KB Output is correct
3 Correct 58 ms 2856 KB Output is correct
4 Correct 53 ms 2640 KB Output is correct
5 Correct 46 ms 4176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 58 ms 2896 KB Output is correct
7 Correct 58 ms 2880 KB Output is correct
8 Correct 58 ms 2856 KB Output is correct
9 Correct 53 ms 2640 KB Output is correct
10 Correct 46 ms 4176 KB Output is correct
11 Correct 52 ms 3920 KB Output is correct
12 Correct 63 ms 3860 KB Output is correct
13 Correct 34 ms 4092 KB Output is correct
14 Correct 57 ms 3920 KB Output is correct
15 Correct 83 ms 11348 KB Output is correct
16 Correct 46 ms 5200 KB Output is correct
17 Correct 16 ms 3892 KB Output is correct
18 Correct 14 ms 3664 KB Output is correct