oj.uz

Submission #600265

# Submission time Handle Problem Language Result Execution time Memory
600265 2022-07-20T15:51:09 Z Shin Building Bridges (CEOI17_building) C++14
100 / 100
 97 ms 11036 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}


struct line_t {
  bool t;
  double in;
  int a; long long b;
  line_t(bool _t = 0, double _in = 0, int _m = 0, long long _c = 0) : t(_t), in(_in), a(_m), b(_c) {}
  long long f(int x) {
    return 1LL * a * x + b;
  }
  bool operator < (const line_t &oth) const {
    if (t || oth.t) {
      return in < oth.in;
    }
    return a > oth.a;
  }
};

struct ConvexHullTrick {
  set<line_t> lns;
  
  long long cdiv(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }

  double inter(line_t ln1, line_t ln2) {
    return (double) (ln1.b - ln2.b) / (ln2.a - ln1.a);
  }

  bool is_keep(set<line_t>::iterator it) {
    if (it == lns.begin() || next(it) == lns.end()) {
      return true;
    }
    if (it != lns.end() && next(it) != lns.end()) {
      if (next(it) -> b <= it -> b) {
        return false;
      }
    }
    return inter(*prev(it), *it) <= inter(*prev(it), *next(it));
  }

  void upd(set<line_t>::iterator it) {
    if (it == lns.begin()) {
      return;
    }
    line_t tmp = *it;
    tmp.in = inter(*prev(it), *it);
    lns.insert(lns.erase(it), tmp);
  }

  void add(int a, long long b) {
    auto it = lns.lower_bound(line_t(0, 0, a, b));
    if (it != lns.end() && it -> a == a) {
      if (it -> b <= b) {
        return;
      }
      lns.erase(it);
    }
    lns.insert(line_t(0, 0, a, b));
    it = lns.lower_bound(line_t(0, 0, a, b));
    if (!is_keep(it)) {
      lns.erase(it);
      return;
    }
    while (it != lns.begin() && !is_keep(prev(it))) {
      lns.erase(prev(it));
    }
    while (it != lns.end() && next(it) != lns.end() && !is_keep(next(it))) {
      lns.erase(next(it));
    }
    if (it != lns.end() && next(it) != lns.end()) {
      upd(next(it));
    }
    upd(it);
  }

  long long get(int x) {
    assert(lns.size() > 0);
    line_t res = *prev(lns.upper_bound(line_t(1, (double) x, 0, 0)));
    return res.f(x);
  }
} cht;

const int N = 1e5 + 7;
int n;
int a[N];
long long dp[N];
long long pref[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i ++) {
    int x; cin >> x;
    pref[i] = pref[i - 1] + x;
  }
  #define SQR(x) 1LL * (x) * (x)
  for (int i = 2; i <= n; i ++) {
    cht.add(-2 * a[i - 1], dp[i - 1] + SQR(a[i - 1]) - pref[i - 1]);
    dp[i] = cht.get(a[i]) + SQR(a[i]) + pref[i - 1];
  }
  cout << dp[n];
  return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2364 KB Output is correct
2 Correct 85 ms 2268 KB Output is correct
3 Correct 80 ms 2244 KB Output is correct
4 Correct 75 ms 3180 KB Output is correct
5 Correct 67 ms 4804 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 79 ms 2364 KB Output is correct
7 Correct 85 ms 2268 KB Output is correct
8 Correct 80 ms 2244 KB Output is correct
9 Correct 75 ms 3180 KB Output is correct
10 Correct 67 ms 4804 KB Output is correct
11 Correct 71 ms 3472 KB Output is correct
12 Correct 87 ms 3280 KB Output is correct
13 Correct 50 ms 3364 KB Output is correct
14 Correct 77 ms 3520 KB Output is correct
15 Correct 97 ms 11036 KB Output is correct
16 Correct 67 ms 4696 KB Output is correct
17 Correct 17 ms 3308 KB Output is correct
18 Correct 16 ms 3284 KB Output is correct