Submission #1071690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071690		quanquai	Building Bridges (CEOI17_building)	C++17	0 / 100	42 ms	3596 KiB

building

/**
 *  author: anonymouse
 *  created: 23.08.2024 15:52:54
**/
#include <bits/stdc++.h>
using namespace std;

struct Line {
  long long a, b;
  Line() : a(0), b(0) {}
  Line(long long _a, long long _b) : a(_a), b(_b) {}
  long long eval(long long x) {
    return a * x + b;
  }
};
struct LiChaoTree {
  int l, r, mid;
  Line func;
  LiChaoTree* left = NULL;
  LiChaoTree* right = NULL;
  LiChaoTree(int _l, int _r) {
    l = _l;
    r = _r;
    mid = (l + r) / 2;
    func = {0, (long long) 1e18};
  } 
  void extend(int t, int _lo, int _hi) {    
    if (t == 0) {
      if (left != NULL) return;
      left = new LiChaoTree(_lo, _hi);
    } else {
      if (right != NULL) return;
      right = new LiChaoTree(_lo, _hi);
    }    
  }
  void ins(Line candidate) {
    if (candidate.eval(mid) < func.eval(mid)) swap(candidate, func);
    if (l + 1 == r) return;
    if (candidate.eval(l) < func.eval(l)) {
      extend(0, l, mid);
      left->ins(candidate);            
    } else {
      extend(1, mid, r);
      right->ins(candidate);
    }
  }
  int64_t get(int x) {
    int64_t ans = func.eval(x);
    if (l + 1 == r) return ans;
    if (x < mid) {
      if (left == NULL) return ans;
      ans = min(ans, left->get(x));
    } else {
      if (right == NULL) return ans;
      ans = min(ans, right->get(x));
    }
    return ans;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n; cin >> n;
  vector<long long> h(n), w(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> w[i];
  }
  LiChaoTree* tree = new LiChaoTree(0, (int) 1e9);
  vector<long long> dp(n);
  dp[0] = -w[0];
  tree->ins(Line((long long) -2 * h[0], h[0] * h[0]));
  for (int i = 1; i < n; i++) {
    dp[i] = tree->get(h[i]) + h[i] * h[i] - w[i];
    tree->ins(Line((long long) -2 * h[i], dp[i] + h[i] * h[i]));
  }  
  cout << accumulate(w.begin(), w.end(), 0ll) + dp[n - 1];

  return 0;
}

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