Submission #703792

#TimeUsernameProblemLanguageResultExecution timeMemory
703792Doncho_BonbonchoBuilding Bridges (CEOI17_building)C++14
100 / 100
109 ms11320 KiB
#include <bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int MAX_N = 1e6; const int INF = 1e9; const int mod = 1e9 + 7; struct Line{ bool type; double x; ll m, c; }; bool operator<( const Line& a, const Line& b ){ if( a.type || b.type ) return a.x < b.x; else return a.m > b.m; } std::set<Line> cht; bool hasPrev( const std::set<Line>::iterator& it ){ return it != cht.begin(); } bool hasNext( const std::set<Line>::iterator& it ){ return it != cht.end() and next(it) != cht.end(); } double intersection( const std::set<Line>::iterator& a, const std::set<Line>::iterator& b ){ return (double)( a -> c - b -> c )/( b -> m - a -> m ); } void calcX( const std::set<Line>::iterator& it ){ if( hasPrev(it) ){ Line l = *it; l.x = intersection( prev(it), it ); cht.insert( cht.erase(it), l ); } } bool bad( const std::set<Line>::iterator& it ){ if( hasNext(it) and next(it) -> c <= it -> c ) return true; return hasNext(it) and hasPrev(it) and intersection( prev(it), next(it) ) <= intersection( prev(it), it ); } void addLine( ll m, ll c ){ std::set<Line>::iterator it; it = cht.lower_bound({ 0, 0, m, c}); if( it != cht.end() and it -> m == m ){ if( it -> c <= c ) return ; cht.erase( it ); } it = cht.insert({0, 0, m, c}).first; if( bad( it ) ) cht.erase(it); else{ while( hasPrev(it) and bad(prev(it)) ) cht.erase(prev(it)); while( hasNext(it) and bad(next(it)) ) cht.erase(next(it)); if( hasNext(it) ) calcX(next(it)); calcX(it); } } ll query( ll h ){ Line l = *prev(cht.upper_bound({1, double(h), 0, 0})); return l.m * h + l.c; } ll dp[MAX_N]; ll h[MAX_N]; ll w[MAX_N]; int main () { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int n; std::cin>>n; ll tot = 0; for( int i=1 ; i<=n ; i++ ) std::cin>>h[i]; for( int i=1 ; i<=n ; i++ ) std::cin>>w[i], tot += w[i]; dp[1] = -w[1]; for( int i=2 ; i<=n ; i++ ){ addLine( -2*h[i-1], dp[i-1] + h[i-1] * h[i-1] ); dp[i] = query( h[i] ) + h[i] * h[i] - w[i]; } std::cout<<dp[n] + tot<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...