oj.uz

Submission #703695

# Submission time Handle Problem Language Result Execution time Memory
703695 2023-02-28T06:40:42 Z mychecksedad Building Bridges (CEOI17_building) C++17
0 / 100
 3000 ms 14636 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 += (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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 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 Execution timed out 3039 ms 14636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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