oj.uz

Submission #705851

# Submission time Handle Problem Language Result Execution time Memory
705851 2023-03-05T13:49:04 Z mychecksedad Building Bridges (CEOI17_building) C++17
100 / 100
 95 ms 11268 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, K = 20;


struct Line{
  bool type;
  double x;
  ll m, c;
  bool operator < (const Line &b) const{
    if(type != b.type) return x < b.x;
    return m > b.m;
  }
};

set<Line> cht;


bool notbegin(const set<Line>::iterator &it){
  return it != cht.begin();
}
bool notend(const set<Line>::iterator &it){
  return it != cht.end() && next(it) != cht.end();
}

double intersection(const set<Line>::iterator &a, const set<Line>::iterator &b){
  return (double) (a->c - b->c) / (b->m - a->m);
} 

void calcX(const set<Line>::iterator &it){
  if(notbegin(it)){
    Line l = *it;
    l.x = intersection(prev(it), it);
    cht.insert(cht.erase(it), l);
  }
}


bool bad(const set<Line>::iterator &it){
  if(notend(it) && next(it)->c <= it->c) return true;
  return notend(it) && notbegin(it) && intersection(prev(it), next(it)) <= intersection(prev(it), it); 
}


void addLine(ll m, ll c){
  auto it = cht.lower_bound({0, 0, m, c});

  if(it != cht.end() && it->m == m){
    if(it->c <= c) return;
    cht.erase(it);
  }
  it = cht.insert({0, 0, m, c}).first;
  if(bad(it)) cht.erase(it);
  else{
    while(notbegin(it) && bad(prev(it))) cht.erase(prev(it));
    while(notend(it) && bad(next(it))) cht.erase(next(it));
    
    if(notend(it)) calcX(next(it));
    calcX(it);
  }
}

ll query(ll h){
  Line l = *prev(cht.upper_bound({1, double(h), 0, 0}));
  return l.m * h + l.c;
}

int n;
ll h[N], w[N], dp[N], sum = 0;
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 = 1; i <= n; ++i) sum += w[i];
  dp[1] = -w[1];
  set<pair<pair<ll, ll>, int>> s; // x end points, r - l - idx

  for(int i = 2; i <= n; ++i){
    addLine(-2*h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
    dp[i] = query(h[i]) + h[i] * h[i] - w[i];
  } 
  cout << dp[n] + sum;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // cin >> T;aa=T;
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
    cout << '\n';
  }
  return 0;
 
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:95:14: warning: unused variable 'aa' [-Wunused-variable]
   95 |   int T = 1, aa;
      |              ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3796 KB Output is correct
2 Correct 75 ms 3840 KB Output is correct
3 Correct 70 ms 3784 KB Output is correct
4 Correct 64 ms 3528 KB Output is correct
5 Correct 59 ms 5128 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 67 ms 3796 KB Output is correct
7 Correct 75 ms 3840 KB Output is correct
8 Correct 70 ms 3784 KB Output is correct
9 Correct 64 ms 3528 KB Output is correct
10 Correct 59 ms 5128 KB Output is correct
11 Correct 59 ms 3904 KB Output is correct
12 Correct 68 ms 3740 KB Output is correct
13 Correct 42 ms 3688 KB Output is correct
14 Correct 75 ms 3852 KB Output is correct
15 Correct 95 ms 11268 KB Output is correct
16 Correct 63 ms 5040 KB Output is correct
17 Correct 19 ms 3668 KB Output is correct
18 Correct 18 ms 3792 KB Output is correct