oj.uz

답안 #710590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710590 2023-03-15T11:50:13 Z ktkerem Building Bridges (CEOI17_building) C++17
100 / 100
 78 ms 65628 KB 
/*#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();
  }
}

Compilation message

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 25 ms 62884 KB Output is correct
3 Correct 24 ms 62932 KB Output is correct
4 Correct 25 ms 62932 KB Output is correct
5 Correct 25 ms 62924 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 65480 KB Output is correct
2 Correct 64 ms 65428 KB Output is correct
3 Correct 66 ms 65544 KB Output is correct
4 Correct 60 ms 65456 KB Output is correct
5 Correct 57 ms 65340 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 25 ms 62884 KB Output is correct
3 Correct 24 ms 62932 KB Output is correct
4 Correct 25 ms 62932 KB Output is correct
5 Correct 25 ms 62924 KB Output is correct
6 Correct 69 ms 65480 KB Output is correct
7 Correct 64 ms 65428 KB Output is correct
8 Correct 66 ms 65544 KB Output is correct
9 Correct 60 ms 65456 KB Output is correct
10 Correct 57 ms 65340 KB Output is correct
11 Correct 78 ms 65612 KB Output is correct
12 Correct 71 ms 65436 KB Output is correct
13 Correct 59 ms 65596 KB Output is correct
14 Correct 74 ms 65628 KB Output is correct
15 Correct 58 ms 65356 KB Output is correct
16 Correct 65 ms 65368 KB Output is correct
17 Correct 53 ms 65496 KB Output is correct
18 Correct 53 ms 65612 KB Output is correct