Submission #703695

#	Time	Username	Problem	Language	Result	Execution time	Memory
703695		mychecksedad	Building Bridges (CEOI17_building)	C++17	0 / 100	3039 ms	14636 KiB

building

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6 + 10, MX = 1e6;


int n;
ll w[N], h[N], c[N], ans = 0;
set<pair<ll, int>> s;
set<int> node;
ll sq(ll x){
  return x*x;
}

void calc(int i){
  int r = *node.upper_bound(i);    
  int l = *(--node.lower_bound(i));    
  c[i] = w[i] - sq(h[l] - h[i]) - sq(h[i] - h[r]) + sq(h[l] - h[r]);
}

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

  for(int i = 2; i <= n; ++i) ans += (h[i]-h[i-1])*(h[i]-h[i-1]);
 
  for(int i = 1; i <= n; ++i) node.insert(i);

  for(int i = 2; i < n; ++i){
    calc(i);
    s.insert({c[i], i});
  }

  while(!s.empty() && (*s.begin()).first < 0){
    auto v = *s.begin();
    ans += v.first;
    node.erase(v.second);
    
    int r = *node.upper_bound(v.second);    
    int l = *(--node.upper_bound(v.second));    

    s.erase(s.begin());
    s.erase({c[l], l});
    s.erase({c[r], r});

    calc(l);
    calc(r);

    s.insert({c[l], l});
    s.insert({c[r], r});
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  solve();
  return 0;
 
}

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