Submission #48422

#TimeUsernameProblemLanguageResultExecution timeMemory
48422wzyBuilding Bridges (CEOI17_building)C++11
100 / 100
195 ms18516 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back long long w[100005] , h[100005]; long long n; long long dp[100005]; struct line{ long long x , y; line(long long x , long long y){ this->x = x , this->y = y; } }; bool operator < (line a , line b){ return a.x > b.x; } template <class type> class CHT{ public : bool cmp(type a , type b , type c){ double f1 = ((c.y) - (a.y)) * ((a.x) - (b.x)) , f2 = ((b.y) - (a.y)) * ((a.x) - (c.x)); return ((long double) (c.y) - (a.y)) * ((long double) (a.x) - (b.x)) <= ((long double) (a.x) - (c.x) )* ((long double) (b.y) - (a.y)) ; return f1 <= f2; } int returnsize(){ return (int) cht.size(); } void addLINE(type a){ while(cht.size() >= 2 && (a.x == cht.back().x || cmp(cht[cht.size() - 2] , cht[cht.size() - 1] , a))){ cht.pop_back(); } cht.push_back(a); } long long eval(type b , int a){ int w = (b.x) * a + (b.y); return w; } long long querymin(int x){ if(cht.size() == 0) return ((long long) 1e18); if(cht.size() <= 5){ int bestvalue = (int) 1e18; for(int i = 0 ; i < cht.size() ; i++) bestvalue = min(bestvalue , eval(cht[i] , x)); return bestvalue; } int l = 0 , r = cht.size() - 1; r--; int ansj = -1; while(l<=r){ int mid = (l+r)/2; if(eval(cht[mid] , x) >= eval(cht[mid + 1] , x)){ l = mid + 1; ansj = mid; } else r = mid - 1; } long long bestvalue = eval(cht.front() , x); if(ansj != -1) bestvalue = min(bestvalue , eval(cht[ansj] , x)); ansj ++; if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x)); for(int i = ansj - 20 ; i <= ansj + 20 ; i++){ if(cht.size() > i && i >=0) bestvalue = min(bestvalue , eval(cht[i] , x)); } return bestvalue; } void mergev(vector<type> nhcht){ vector<type> newcht; reverse(nhcht.begin() , nhcht.end()); reverse(cht.begin() , cht.end()); while(cht.size() && nhcht.size()){ if(cht.back().x == nhcht.back().x){ if(cht.back().y > nhcht.back().y) newcht.pb(cht.back()) , cht.pop_back(); else newcht.pb(nhcht.back()) , nhcht.pop_back(); } else if(cht.back().x >= nhcht.back().x) newcht.pb(cht.back()) , cht.pop_back(); else newcht.pb(nhcht.back()) , nhcht.pop_back(); } while(cht.size()){ newcht.pb(cht.back()) , cht.pop_back(); } while(nhcht.size()) newcht.pb(nhcht.back()) , nhcht.pop_back(); for(int i = 0 ; i < ((int)newcht.size()) - 1 ; i++){ assert(newcht[i].x >= newcht[i+1].x); } for(int i = 0 ; i < newcht.size() ; i++) addLINE(newcht[i]); } vector<type> mergefunc(){ return cht; } void clearv(){ cht.clear(); } long long querymax(int x){ if(cht.size() == 0) return -(int) 1e18; int l = 0 , r = cht.size() - 1; r--; int ansj = -1; while(l<=r){ int mid = (l+r)/2; if(eval(cht[mid] , x) <= eval(cht[mid+1],x)){ l = mid + 1; ansj = mid; } else r = mid - 1; } long long bestvalue = eval(cht.front() , x); if(ansj != -1) bestvalue = max(bestvalue , eval(cht[ansj] , x)); ansj++; if(ansj < cht.size()) bestvalue = max(bestvalue ,eval(cht[ansj] , x)); return bestvalue; } // private : vector<type> cht; }; CHT<line> chts[32]; void addline(line a){ vector<line> newcht; newcht.pb(a); chts[0].mergev(newcht); for(int i = 0 ; i < 32 ; i++){ int z = (1LL<<i); if((chts[i].returnsize()) >= z){ chts[i+1].mergev(chts[i].mergefunc()); chts[i].clearv(); } } } long long query(int x){ long long bestvalue = (long long) 1e18; for(int i = 0 ; i < 32 ; i++){ if(chts[i].returnsize() != 0) bestvalue = min(bestvalue , chts[i].querymin(x)); } return bestvalue; } int32_t main(){ scanf("%lld" , &n); dp[0] = 0; for(int i = 1 ; i <=n ;i ++){ scanf("%lld" , &h[i]); } w[0] = 0; for(int i = 1 ; i <=n ;i ++){ scanf("%lld" , &w[i]); w[i] += w[i-1]; } dp[1] = 0; addline(line(-2*h[1] , h[1]*h[1] - w[1] )); for(int i = 2 ; i <= n ;i ++){ dp[i] = query(h[i]) + h[i]*h[i] + w[i-1]; addline(line(-2*h[i] , h[i]*h[i] - w[i] + dp[i])); } printf("%lld\n" , dp[n]); }

Compilation message (stderr)

building.cpp: In instantiation of 'void CHT<type>::mergev(std::vector<_Tp>) [with type = line]':
building.cpp:122:23:   required from here
building.cpp:85:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i = 0 ; i < newcht.size() ; i++) addLINE(newcht[i]);
building.cpp: In instantiation of 'long long int CHT<type>::querymin(long long int) [with type = line]':
building.cpp:138:49:   required from here
building.cpp:42:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for(int i = 0 ; i < cht.size() ; i++) bestvalue = min(bestvalue , eval(cht[i] , x));
building.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));
building.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          if(cht.size() > i && i >=0) bestvalue = min(bestvalue , eval(cht[i] , x));
building.cpp: In function 'int32_t main()':
building.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
  ~~~~~^~~~~~~~~~~~~
building.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &h[i]);
   ~~~~~^~~~~~~~~~~~~~~~
building.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...