Submission #61828

#TimeUsernameProblemLanguageResultExecution timeMemory
61828IvanCBuilding Bridges (CEOI17_building)C++17
100 / 100
682 ms16208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int MAXN = 1e5 + 10; const int BUCKET = 320; const ll INF = 1e18; struct line{ ll a,b; line(ll _a = 0,ll _b = 0){ a = _a; b = _b; } ll get(ll x){return a*x + b;} ld get_ld(ld x){return a*x + b;} bool operator<(const line& other)const{ if(a != other.a) return a > other.a; return b > other.b; } }; vector<line> hull,light_lines; ll dp[MAXN],H[MAXN],W[MAXN],pref[MAXN],b[MAXN],a[MAXN]; int N; ld inter(line l1,line l2){ return -1.0*ld(l1.b - l2.b)/ld(l1.a - l2.a); } bool useless(line l1,line l2,line l3){ ld x = inter(l1,l3); return l2.get_ld(x) > l3.get_ld(x); } void add_line(line l){ while(!hull.empty() && hull.back().a == l.a){ hull.pop_back(); } while(hull.size() >= 2 && useless(hull[hull.size()-2],hull.back(),l)){ hull.pop_back(); } hull.push_back(l); } void rebuild(){ vector<line> temp; sort(light_lines.begin(),light_lines.end()); merge(hull.begin(),hull.end(),light_lines.begin(),light_lines.end(),back_inserter(temp)); hull.clear(); light_lines.clear(); for(line l : temp){ add_line(l); } } void add(ll a,ll b){ line l(a,b); light_lines.push_back(l); if(light_lines.size() >= BUCKET) rebuild(); } ll query(ll x){ ll ans = INF; for(line l : light_lines) ans = min(ans, l.get(x) ); if(hull.empty()) return ans; ans = min(ans, hull.back().get(x) ); int ini = 0,fim = hull.size() - 2,meio; while(ini <= fim){ meio = ini + (fim - ini)/2; ll f1 = hull[meio].get(x),f2 = hull[meio+1].get(x); ans = min(ans, min(f1,f2) ); if(f1 < f2){ fim = meio - 1; } else{ ini = meio + 1; } } return min(ans,hull[meio].get(x)); } int main(){ scanf("%d",&N); for(int i = 1;i<=N;i++){ scanf("%lld",&H[i]); } for(int i = 1;i<=N;i++){ scanf("%lld",&W[i]); pref[i] = W[i] + pref[i-1]; } dp[1] = 0; a[1] = -2*H[1]; b[1] = -pref[1] + dp[1] + H[1]*H[1]; add(a[1],b[1]); for(int i = 2;i<=N;i++){ dp[i] = query(H[i]) + H[i]*H[i] + pref[i-1]; a[i] = -2*H[i]; b[i] = -pref[i] + dp[i] + H[i]*H[i]; add(a[i],b[i]); } cout << dp[N] << endl; return 0; }

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
building.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&H[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&W[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp: In function 'll query(ll)':
building.cpp:78:36: warning: 'meio' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ini = 0,fim = hull.size() - 2,meio;
                                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...