Submission #1200009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200009		lopkus	Building Bridges (CEOI17_building)	C++20	100 / 100	80 ms	81736 KiB

building

#include <bits/stdc++.h>

#define int int64_t

const int M = 1e9;

const int inf = 1e18;

struct Line {
  int k, n;
  bool active = false;
  int get(int x) {
    return k * x + n;
  }
};

const int N = 2e6 + 5;

Line t[N];
std::vector<int> ll(N);
std::vector<int> rr(N);

struct CHT {
  int New = 2;
  void add(int c, int tl, int tr, Line line) {
    if(!t[c].active) {
      t[c] = line;
      return;
    }
    int mid = (tl + tr) / 2;
    int oldtl = t[c].get(tl);
    int oldmid = t[c].get(mid);
    int oldtr = t[c].get(tr);
    int newtl = line.get(tl);
    int newmid = line.get(mid);
    int newtr = line.get(tr);
    if(oldtl <= newtl && oldtr <= newtr) {
      return;
    }
    if(newtl <= oldtl && newtr <= oldtr) {
      t[c] = line;
      return;
    }
    if(newmid < oldmid) {
      std::swap(t[c], line);
    }
    if(tl == tr) {
      return;
    }
    if(!ll[c]) {
      ll[c] = New++;
    }
    if(!rr[c]) {
      rr[c] = New++;
    }
    if(t[c].get(tl) > line.get(tl)) {
      add(ll[c], tl, mid, line);
    }
    else {
      add(rr[c], mid + 1, tr, line);
    }
  }
  int query(int c, int tl, int tr, int x) {
    if(tl > x || tr < x || tl > tr || t[c].active == false) {
      return inf;
    }
    int now = t[c].get(x);
    if(tl == tr) {
      return now;
    }
    if(!ll[c]) {
      ll[c] = New++;
    }
    if(!rr[c]) {
      rr[c] = New++;
    }
    int mid = (tl + tr) / 2;
    return std::min({query(ll[c], tl, mid, x), query(rr[c], mid + 1, tr, x), now});
  }
}cht;

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> h(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> h[i];
  }
  std::vector<int> w(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> w[i];
  }
  std::vector<int> pref(n + 1);
  for(int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + w[i];
  }
  std::vector<int> dp(n + 1, inf);
  dp[1] = 0;
  Line uio;
  uio.active = true;
  uio.k = h[1];
  uio.n = dp[1] + h[1] * h[1] - pref[1];
  cht.add(1, -M, + M, uio);
  for(int i = 2; i <= n; i++) {
    dp[i] = h[i] * h[i] + pref[i - 1] + cht.query(1, -M, + M, - 2 * h[i]);
    Line L;
    L.active = true;
    L.k = h[i];
    L.n = dp[i] + h[i] * h[i] - pref[i];
    cht.add(1, - M, M, L);
  }
  std::cout << dp[n];
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

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