This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |