#include<iostream>
#include<stdio.h>
#include<set>
using namespace std ;
#define MAXN 100007
#define eps 0.00001
long long inf = (long long)1e18 + 7 ;
int n ;
long long a[ MAXN ] ;
long long b[ MAXN ] ;
long long pref[ MAXN ] ;
long long dp[ MAXN ] ;
struct CHT {
struct line {
long long coef , add ;
double nxt_x ;
int is_query ;
line ( ) { coef = add = nxt_x = is_query = 0 ; }
line ( long long _coef , long long _add ) {
coef = _coef ;
add = _add ;
nxt_x = 0 ;
is_query = 0 ;
}
bool operator < ( const line other ) const {
if ( is_query == 0 && other.is_query == 0 ) { return ( coef > other.coef ) ; }
return ( nxt_x < other.nxt_x ) ;
}
long long value_at ( long long x ) const {
return ( x * coef + add ) ;
}
};
bool parallel ( line p1 , line p2 ) {
return ( p1.coef == p2.coef ) ;
}
double intersect ( line p1 , line p2 ) {
if ( parallel ( p1 , p2 ) == true ) { return inf ; }
///printf ( "--- %lld %lld with %lld %lld\n" , p1.coef , p1.add , p2.coef , p2.add ) ;
return ( ( (double)( p2.add - p1.add ) ) / ( p1.coef - p2.coef ) ) ;
}
set < line > s ;
void init ( ) { s.clear ( ) ; }
bool has_nxt ( set < line > :: iterator it ) {
if ( it == s.end ( ) ) { return false ; }
it ++ ;
if ( it == s.end ( ) ) { return false ; }
return true ;
}
bool has_prv ( set < line > :: iterator it ) {
if ( it == s.end ( ) ) { return false ; }
if ( it == s.begin ( ) ) { return false ; }
return true ;
}
set < line > :: iterator get_nxt ( set < line > :: iterator it ) {
it ++ ; return it ;
}
set < line > :: iterator get_prv ( set < line > :: iterator it ) {
it -- ; return it ;
}
bool needless ( line p1 , line p2 , line p3 ) {
double cross1 = intersect ( p1 , p2 ) ;
double cross2 = intersect ( p1 , p3 ) ;
return ( cross2 < cross1 + eps ) ;
}
bool needless ( set < line > :: iterator it ) {
if ( has_prv ( it ) == false ) { return false ; }
if ( has_nxt ( it ) == false ) { return false ; }
return needless ( *get_prv ( it ) , *it , *get_nxt ( it ) ) ;
}
set < line > :: iterator update ( set < line > :: iterator it ) {
line aux = (*it) ;
double ret = inf ;
if ( has_nxt ( it ) == true ) { ret = intersect ( (*it) , *get_nxt ( it ) ) ; }
///printf ( "%.12f\n" , ret ) ;
it = s.erase ( it ) ;
aux.nxt_x = ret ;
it = s.insert ( it , aux ) ;
///printf ( "%.12f\n" , it->nxt_x ) ;
return it ;
}
void add_line ( long long _coef , long long _add ) {
line nw = line ( _coef , _add ) ;
set < line > :: iterator it = s.lower_bound ( nw ) ;
if ( it != s.end ( ) && it->coef == nw.coef ) {
if ( it->add <= nw.add ) { return ; }
it = s.erase ( it ) ;
}
it = s.insert ( it , nw ) ;
if ( needless ( it ) == true ) {
s.erase ( it ) ; return ;
}
while ( has_prv ( it ) == true && needless ( get_prv ( it ) ) == true ) { s.erase ( get_prv ( it ) ) ; }
while ( has_nxt ( it ) == true && needless ( get_nxt ( it ) ) == true ) { s.erase ( get_nxt ( it ) ) ; }
it = update ( it ) ;
if ( has_prv ( it ) == true ) { update ( get_prv ( it ) ) ; }
if ( has_nxt ( it ) == true ) { update ( get_nxt ( it ) ) ; }
}
long long query ( long long x ) {
///printf ( "SET SIZE EQUALS %d\n" , s.size ( ) ) ;
line aux = line ( ) ;
aux.nxt_x = x ;
aux.is_query = 1 ;
set < line > :: iterator it = s.lower_bound ( aux ) ;
if ( it == s.end ( ) ) { return inf ; }
///printf ( "--- %f\n" , x ) ;
return it->value_at ( x ) ;
}
};
CHT w ;
void input ( ) {
scanf ( "%d" , &n ) ;
int i ;
for ( i = 1 ; i <= n ; i ++ ) {
scanf ( "%lld" , &a[ i ] ) ;
}
for ( i = 1 ; i <= n ; i ++ ) {
scanf ( "%lld" , &b[ i ] ) ;
pref[ i ] = ( pref[ i - 1 ] + b[ i ] ) ;
}
}
void solve ( ) {
w.init ( ) ;
int i ;
w.add_line ( -2 * a[ 1 ] , a[ 1 ] * a[ 1 ] - pref[ 1 ] ) ;
for ( i = 2 ; i <= n ; i ++ ) {
long long ret = w.query ( a[ i ] ) ;
dp[ i ] = ret + a[ i ] * a[ i ] + pref[ i - 1 ] ;
///printf ( "%lld, dp[ %d ] = %lld\n" , ret , i , dp[ i ] ) ;
w.add_line ( -2 * a[ i ] , dp[ i ] + a[ i ] * a[ i ] - pref[ i ] ) ;
}
printf ( "%lld\n" , dp[ n ] ) ;
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/
Compilation message
building.cpp: In function 'void input()':
building.cpp:123:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d" , &n ) ;
~~~~~~^~~~~~~~~~~~~
building.cpp:126:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%lld" , &a[ i ] ) ;
~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:129:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%lld" , &b[ i ] ) ;
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
408 KB |
Output is correct |
| 4 |
Correct |
10 ms |
408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
3888 KB |
Output is correct |
| 2 |
Correct |
121 ms |
4772 KB |
Output is correct |
| 3 |
Correct |
110 ms |
5840 KB |
Output is correct |
| 4 |
Correct |
106 ms |
6952 KB |
Output is correct |
| 5 |
Correct |
108 ms |
9296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
408 KB |
Output is correct |
| 4 |
Correct |
10 ms |
408 KB |
Output is correct |
| 5 |
Correct |
3 ms |
596 KB |
Output is correct |
| 6 |
Correct |
181 ms |
3888 KB |
Output is correct |
| 7 |
Correct |
121 ms |
4772 KB |
Output is correct |
| 8 |
Correct |
110 ms |
5840 KB |
Output is correct |
| 9 |
Correct |
106 ms |
6952 KB |
Output is correct |
| 10 |
Correct |
108 ms |
9296 KB |
Output is correct |
| 11 |
Correct |
102 ms |
9296 KB |
Output is correct |
| 12 |
Correct |
132 ms |
10040 KB |
Output is correct |
| 13 |
Correct |
78 ms |
11048 KB |
Output is correct |
| 14 |
Correct |
127 ms |
12268 KB |
Output is correct |
| 15 |
Correct |
119 ms |
21088 KB |
Output is correct |
| 16 |
Correct |
88 ms |
21088 KB |
Output is correct |
| 17 |
Correct |
28 ms |
21088 KB |
Output is correct |
| 18 |
Correct |
33 ms |
21088 KB |
Output is correct |
