제출 #582929

#제출 시각아이디문제언어결과실행 시간메모리
582929600MihneaBuilding Bridges (CEOI17_building)C++17
100 / 100
121 ms102148 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const ll INF = (ll) 1e18 + 7;

struct T {
  ll a;
  ll b;
  bool mt = 1;

  T() {

  }

  T(ll a, ll b) : a(a), b(b) {
  }

  ll evaluate(ll x) {
    if (mt) {
      return INF;
    }
    return a * x + b;
  }
};

const int N = (int) 1e5 + 7;
const int DIM = (int) 1e6 + 7;
int n;
ll h[N];
ll sum[N];
ll dp[N];
T coef[N];
T tree[4 * DIM];

void addLine(int v, int tl, int tr, T line) {
  if (line.evaluate(tl) <= tree[v].evaluate(tl) && line.evaluate(tr) <= tree[v].evaluate(tr)) {
    tree[v] = line;
    return;
  }
  if (tree[v].evaluate(tl) <= line.evaluate(tl) && tree[v].evaluate(tr) <= line.evaluate(tr)) {
    return;
  }
  assert(tl < tr);
  int tm = (tl + tr) / 2;
  if (line.evaluate(tl) < tree[v].evaluate(tl)) {
    swap(line, tree[v]);
  }
  assert(tree[v].evaluate(tl) <= line.evaluate(tl));
  if (tree[v].evaluate(tm) <= line.evaluate(tm)) {
    addLine(2 * v + 1, tm + 1, tr, line);
  } else {
    swap(line, tree[v]);
    addLine(2 * v, tl, tm, line);
  }
}

ll get(int v, int tl, int tr, int x) {
  if (x < tl || tr < x) {
    return INF;
  }
  ll sol = tree[v].evaluate(x);
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    sol = min(sol, get(2 * v, tl, tm, x));
    sol = min(sol, get(2 * v + 1, tm + 1, tr, x));
  }
  return sol;
}

void addLine(T line) {
  addLine(1, 0, (int) 1e6, line);
}

ll get(int x) {
  return get(1, 0, (int) 1e6, x);
}

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

 /// freopen ("input.txt", "r", stdin);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    h[i] = x;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    sum[i] = sum[i - 1] + x;
  }

  dp[1] = 0;
  for (int i = 2; i <= n; i++) {
    dp[i] = INF;
  }

  vector<T> all;

  for (int r = 2; r <= n; r++) {
    T line = {- 2 * h[r - 1], dp[r - 1] + h[r - 1] * h[r - 1] - sum[r - 1]};
    line.mt = 0;

    all.push_back(line);
    addLine(line);

    dp[r] = get(h[r]);

    dp[r] += h[r] * h[r] + sum[r - 1];
  }
  cout << dp[n] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...