oj.uz

Submission #1113082

# Submission time Handle Problem Language Result Execution time Memory
1113082 2024-11-15T16:43:40 Z available3124 Building Bridges (CEOI17_building) C++14
100 / 100
 87 ms 11336 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define int long long

const int maxn = 2e5;

struct convex_hull {

  struct Line {
    bool type;
    double x;
    int m, c;

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

  set<Line> cht;
  bool has_prev(set<Line>::iterator t) {
    return t != cht.begin();
  }
  bool has_next(set<Line>::iterator t) {
    return t != cht.end() && next(t) != cht.end();
  }
  double interect(set<Line>::iterator l1, set<Line>::iterator l2) {
    return (double)(l1->c - l2->c) / (l2->m - l1->m);
  }

  void calc_x(set<Line>::iterator t) {
    if (has_prev(t)) {
      Line l = *t;
      l.x = interect(prev(t), t);
      cht.insert(cht.erase(t), l);
    }
  }

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

  void add_line(ll m, ll c) {
    set<Line>::iterator it;

    it = cht.lower_bound({0, 0, m, c});
    if (it != cht.end() && it->m == m) {
      if (it->c <= c) {
        return;
      }
      cht.erase(it);
    }

    it = cht.insert({0, 0, m, c}).first;
    if (bad(it)) {
      cht.erase(it);
    } else {
      while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
      while (has_next(it) && bad(next(it))) cht.erase(next(it));

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


  int query(int h) {
    Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
    return l.m * h + l.c;
  }
};

struct Rect {
  int x, y;

  const bool operator<(const Rect &r) {
    return x < r.x || (x == r.x && y > r.y);
  }
};


signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, tot = 0;

  cin >> n;
  vector<int> h(n + 1);

  for (int i = 1; i <= n; i++) cin >> h[i];

  vector<int> w(n + 1);
  vector<int> dp(n + 1);
  for (int i = 1; i <= n; i++) {

    cin >> w[i];

    tot += w[i];

  }


  dp[1] = -w[1];

  convex_hull 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];

  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 464 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 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3912 KB Output is correct
2 Correct 54 ms 3872 KB Output is correct
3 Correct 57 ms 3912 KB Output is correct
4 Correct 51 ms 3784 KB Output is correct
5 Correct 51 ms 5064 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 464 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 504 KB Output is correct
6 Correct 54 ms 3912 KB Output is correct
7 Correct 54 ms 3872 KB Output is correct
8 Correct 57 ms 3912 KB Output is correct
9 Correct 51 ms 3784 KB Output is correct
10 Correct 51 ms 5064 KB Output is correct
11 Correct 59 ms 3920 KB Output is correct
12 Correct 71 ms 3784 KB Output is correct
13 Correct 36 ms 3920 KB Output is correct
14 Correct 59 ms 3980 KB Output is correct
15 Correct 87 ms 11336 KB Output is correct
16 Correct 52 ms 5192 KB Output is correct
17 Correct 18 ms 3664 KB Output is correct
18 Correct 17 ms 3652 KB Output is correct