Submission #63156

#TimeUsernameProblemLanguageResultExecution timeMemory
63156khsoo01Building Bridges (CEOI17_building)C++11
100 / 100
206 ms17336 KiB
#include<bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll N = 100005, L = 18, inf = 1e18; ll n, def, h[N], a[N], d[N]; ll val (pll &P, ll V) {return P.X*V+P.Y;} bool valid (pll &A, pll &B, pll &C) { return (B.Y-A.Y) * (B.X-C.X) < (C.Y-B.Y) * (A.X-B.X); } struct hull { vector<pll> v; void upd (pll P) { for(ll i=v.size();i--;) { if(v[i].X != P.X) break; else v.pop_back(); } for(ll i=v.size();i-->1;) { if(valid(v[i-1], v[i], P)) break; else v.pop_back(); } v.push_back(P); } ll get (ll P) { if(v.empty()) return inf; ll S = 0, E = (int)v.size()-1; while(S<E) { ll M = (S+E)/2; val(v[M], P) < val(v[M+1], P) ? E = M : S = M+1; } return val(v[S], P); } } x[L]; void Merge (hull &A, hull &B) { vector<pll> V; for(int i=0,j=0;i<A.v.size()||j<B.v.size();) { bool flag = false; if(i == A.v.size()) flag = true; else if(j == B.v.size()) flag = false; else if(A.v[i] < B.v[j]) flag = true; if(flag) {V.push_back(B.v[j]); j++;} else {V.push_back(A.v[i]); i++;} } A.v.clear(); B.v.clear(); for(auto &T : V) A.upd(T); } int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&h[i]); for(ll i=1;i<=n;i++) {scanf("%lld",&a[i]); def += a[i];} x[0].upd(pll(-2*h[1], h[1]*h[1]-a[1])); for(ll i=2;i<=n;i++) { d[i] = inf; for(ll j=0;j<L;j++) { d[i] = min(d[i], x[j].get(h[i])-a[i]+h[i]*h[i]); } hull tmp; tmp.upd(pll(-2*h[i], h[i]*h[i]+d[i])); for(ll j=0;j<L;j++) { if(x[j].v.empty()) {swap(x[j], tmp); break;} else Merge(tmp, x[j]); } } printf("%lld\n",d[n]+def); }

Compilation message (stderr)

building.cpp: In function 'void Merge(hull&, hull&)':
building.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<A.v.size()||j<B.v.size();) {
                  ~^~~~~~~~~~~
building.cpp:43:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<A.v.size()||j<B.v.size();) {
                                ~^~~~~~~~~~~
building.cpp:45:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == A.v.size()) flag = true;
      ~~^~~~~~~~~~~~~
building.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(j == B.v.size()) flag = false;
           ~~^~~~~~~~~~~~~
building.cpp: In function 'int main()':
building.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
building.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=n;i++) scanf("%lld",&h[i]);
                       ~~~~~^~~~~~~~~~~~~~
building.cpp:59:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=n;i++) {scanf("%lld",&a[i]); def += a[i];}
                        ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...