Submission #1194189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194189		giknes	Building Bridges (CEOI17_building)	C++20	100 / 100	55 ms	9800 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pt pair<int, int>
#define ft first
#define sc second
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()

struct Line{
  bool type;
  double x = 0;
  int k = 0;
  int b = 0;
};

set<Line> cht;

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

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

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();
}

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

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);
  }
}

void add_line(int k, int b){
  set<Line>::iterator it;
  it = cht.lower_bound({0, 0, k, b});
  if (it != cht.end() && it->k == k){
    if (it->b <= b){
      return;
    }
    cht.erase(it);
  }
  it = cht.insert({0, 0, k, b}).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);
  }
}

int get(int x){
  auto it = prev(cht.upper_bound({1, double(x), 0, 0}));
  return it->k * x + it->b;
}

void solve() {
  int n;
  cin >> n;
  vector<int> h(n + 1), w(n + 1);
  for (int i = 1; i <= n; ++i){
    cin >> h[i];
  }
  int total = 0;
  for (int i = 1; i <= n; ++i){
    cin >> w[i];
    total += w[i];
  }
  int ans = -w[1];
  for (int i = 2; i <= n; ++i){
    add_line(-2 * h[i - 1], ans + h[i - 1] * h[i - 1]);
    ans = get(h[i]) + h[i] * h[i] - w[i];
  }
  cout << total + ans;
}
 
int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int test = 1;
  while (test--) {
    solve();
  }
}

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