oj.uz

Submission #600268

# Submission time Handle Problem Language Result Execution time Memory
600268 2022-07-20T15:53:36 Z Shin Building Bridges (CEOI17_building) C++14
100 / 100
 99 ms 10000 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;
  long long in;
  int a; long long b;
  line_t(bool _t = 0, long long _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 - 1) / b;
  }
 
  long long inter(line_t ln1, line_t ln2) {
    return cdiv(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;
    }
    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, 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 1 ms 264 KB Output is correct
2 Correct 0 ms 340 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 73 ms 2296 KB Output is correct
2 Correct 73 ms 2252 KB Output is correct
3 Correct 84 ms 2360 KB Output is correct
4 Correct 81 ms 2284 KB Output is correct
5 Correct 82 ms 3888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 264 KB Output is correct
2 Correct 0 ms 340 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 73 ms 2296 KB Output is correct
7 Correct 73 ms 2252 KB Output is correct
8 Correct 84 ms 2360 KB Output is correct
9 Correct 81 ms 2284 KB Output is correct
10 Correct 82 ms 3888 KB Output is correct
11 Correct 64 ms 2276 KB Output is correct
12 Correct 75 ms 2296 KB Output is correct
13 Correct 52 ms 2236 KB Output is correct
14 Correct 75 ms 2276 KB Output is correct
15 Correct 99 ms 10000 KB Output is correct
16 Correct 77 ms 3944 KB Output is correct
17 Correct 21 ms 2236 KB Output is correct
18 Correct 14 ms 2168 KB Output is correct