oj.uz

Submission #703698

# Submission time Handle Problem Language Result Execution time Memory
703698 2023-02-28T06:48:04 Z mychecksedad Building Bridges (CEOI17_building) C++17
0 / 100
 351 ms 13640 KB 
/* 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.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 13636 KB Output is correct
2 Incorrect 351 ms 13640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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