제출 #703698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703698		mychecksedad	Building Bridges (CEOI17_building)	C++17	0 / 100	351 ms	13640 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);    
  auto it = node.lower_bound(i); it--;
  int l = *it;    
  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 += sq(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);    
    auto it = node.upper_bound(v.second); --it;
    int l = *it;    

    s.erase(s.begin());
    if(l > 1){
      s.erase({c[l], l});
      calc(l);
      s.insert({c[l], l});
    }
    if(r < n){
      s.erase({c[r], r}); 
      calc(r);
      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