oj.uz

Submission #1071690

# Submission time Handle Problem Language Result Execution time Memory
1071690 2024-08-23T10:02:46 Z quanquai Building Bridges (CEOI17_building) C++17
0 / 100
 42 ms 3596 KB 
/**
 *  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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 3596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -