제출 #710590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710590		ktkerem	Building Bridges (CEOI17_building)	C++17	100 / 100	78 ms	65628 KiB

building

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e9+7;
const ll sus = 1e6 + 5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
  return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n;
std::vector<ll> ar , br;
std::vector<vec> valt;
/**/
/*functions*/
ftyp dot(vec a , vec b){
  return (std::conj(a) * b).cy();
}
void addLine(vec dd , ftyp l , ftyp r , ll a){
  ll md = (l + r + 1)/2;
  ll fo = dot(dd , {l , 1}) < dot(valt[a] , {l , 1}) , so = dot(dd , {md , 1}) < dot(valt[a] , {md , 1});
  //std::cout << l << " " << r << " " << dd.cx() << " " << dd.cy() << "\n";
  if(so){
    std::swap(valt[a] , dd);
  }
  if(l >= r){
    return;
  }
  if(fo != so){
    addLine(dd , l , md-1 , a*2);
  }
  else{
    addLine(dd , md , r , a*2+1);
  }
}
ftyp gt(ll x , ll l , ll r , ll a){
  ll md = (l + r + 1)/2;
  if(l >= r){
    /*std::cout << valt[a].cx() << " " << valt[a].cy() << "\n";
    std::cout << dot(valt[a] , {x , 1}) << "\n";*/
    return dot(valt[a] , {x , 1});
  }
  else if(md > x){
    return std::min(dot(valt[a] , {x , 1}) , gt(x , l , md-1 , a*2));
  }
  else{
    return std::min(dot(valt[a] , {x , 1}) , gt(x , md , r , a*2+1)); 
  }
}
/**/
void solve(){
  std::cin >> n;
  ar.resize(n);
  br.resize(n);
  for(ll i = 0 ; n>i;i++){
    std::cin >> ar[i];
  }
  ll sm = 0;
  for(ll i = 0 ; n>i;i++){
    std::cin >> br[i];
    sm+=br[i];
  }
  valt.resize(sus*4 , {(ar[0] * ar[0]) - br[0] , 2 * ar[0]});
  ll ans = 0;
  for(ll i = 1;n>i;i++){
    ll a = gt(ar[i] , 0 , sus , 1);
    ans = ar[i] * ar[i] + a - br[i];
    addLine({ans + ar[i] * ar[i] , 2 * ar[i]} , 0 , sus , 1);
    /*std::cout << a << "\n";
    std::cout << ans  << "\n";
    std::cout << std::endl;*/
  }
  std::cout << ans + sm;
  return;/**/
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  /*#ifndef ONLINE_JUDGE
    freopen("in.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
  #endif*/
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}

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

building.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

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