제출 #699860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699860		VietThang	Building Bridges (CEOI17_building)	C++17	100 / 100	91 ms	11332 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define task "BUILD"

#define sz(x) (int)x.size()

const int N = 1e5 + 3;
const long long inf = 1e18;

long long dp[N];
long long pref[N];
int h[N], w[N];
int n;

long long sqr(int x) {
  return 1ll * x * x;
}

namespace sub1 {
  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
//    dp[2] = sqr(h[2] - h[1]);
    for (int i = 2; i <= n; i++) {
      for (int j = i - 1; j >= 1; j--)
        dp[i] = min(dp[i], dp[j] + sqr(h[i] - h[j]) + (pref[i] - pref[j] - w[i]));
    }
    cout << dp[n];
  }
}

long long Res = inf;

namespace sub2 {
  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
    if (n != 1) Res = min(Res, sqr(h[n] - h[1]) + (pref[n] - pref[1] - w[n]));
    for (int i = 2; i <= n; i++) {
      if (i != n) {
          Res = min(Res, sqr(h[i] - h[1]) + sqr(h[i] - h[n])
                + (pref[i] - pref[1] - w[i]) + (pref[n] - pref[i] - w[n]));
      }
      for (int j = i - 1; j >= max(1, i - 1001); j--)
        dp[i] = min(dp[i], dp[j] + sqr(h[i] - h[j]) + (pref[i] - pref[j] - w[i]));
    }
    Res = min(Res, dp[n]);
  }
}

namespace sub3 {
  struct Line {
    bool type;
    double x;
    long long m, c;
  };

  bool operator<(Line l1, Line l2) {
    if (l1.type || l2.type) return l1.x < l2.x;
    return l1.m > l2.m;
  }

  set<Line> cht;

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

  double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
    return (double)(l1->c - l2->c) / (l2->m - l1->m);
  }

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

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

  void add_line(long long m, long long 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);
    }
  }

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

  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
    add_line(-2 * h[1], -pref[1] + sqr(h[1]));
    for (int i = 2; i <= n; i++) {
      dp[i] = query(h[i]) + sqr(h[i]) + pref[i] - w[i];
      add_line(-2 * h[i], dp[i] - pref[i] + sqr(h[i]));
    }
    Res = min(Res, dp[n]);
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> h[i];
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    pref[i] = pref[i - 1] + w[i];
  }

//  if (n <= 1000) sub1::sol();
//  else {
    Res = inf;
//    sub2::sol();
    sub3::sol();
    cout << Res;
//  }
}

int main() {
//  freopen(task".inp", "r", stdin);
//  freopen(task".out", "w", stdout);
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tc = 1;
//  cin >> tc; cin.ignore();
  while (tc--)
    solve();
  return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40