제출 #705851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705851		mychecksedad	Building Bridges (CEOI17_building)	C++17	100 / 100	95 ms	11268 KiB

building

/* 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;
 
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40