oj.uz

Submission #703696

# Submission time Handle Problem Language Result Execution time Memory
703696 2023-02-28T06:44:07 Z mychecksedad Building Bridges (CEOI17_building) C++17
0 / 100
 344 ms 14664 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);    
  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 += 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);    
    int l = *(--node.upper_bound(v.second));    

    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 334 ms 13632 KB Output is correct
2 Incorrect 344 ms 14664 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 -