#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
int n;
long long sum[M], h[M], dp[M];
pll seg[4*N], zero;
long long get( pll a, long long x ) { return a.x * x + a.y; }
void update( pll li, int l = 1, int r = N - 9, int idx = 1 ) {
if( seg[idx] == zero ) return void( seg[idx] = li );
if( get( li, l ) <= get( seg[idx], l ) && get( li, r ) <= get( seg[idx], r ) ) return void( seg[idx] = li );
if( get( li, l ) >= get( seg[idx], l ) && get( li, r ) >= get( seg[idx], r ) ) return ;
if( l == r ) return ;
int mid = l + r >> 1;
if( get( li, l ) >= get( seg[idx], l ) ) swap( seg[idx], li );
if( get( li, mid ) >= get( seg[idx], mid ) ) update( li, l, mid, idx<<1 );
else swap( seg[idx], li ), update( li, mid + 1, r, idx<<1|1 );
}
long long query( long long x, int l = 1, int r = N - 9, int idx = 1 ) {
if( seg[idx] == zero ) return 1e18;
if( l == r ) return get( seg[idx], x );
int mid = l + r >> 1;
if( idx <= mid ) return min( query( x, l, mid, idx<<1 ), get( seg[idx], x ) );
else return min( get( seg[idx], x ), query( x, mid + 1, r, idx<<1|1 ) );
}
int main()
{
zero = pll( ( long long)-1e18, ( long long )-1e18 );
scanf("%d",&n);
for( int i = 1 ; i < 4*N ; i++ ) seg[i] = zero;
for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&h[i]);
for( int i = 1 ; i <= n ; i++ ) {
scanf("%lld",&sum[i]);
sum[i] += sum[i-1];
}
for( int i = 1 ; i <= n ; i++ ) {
if( i > 1 ) dp[i] = query( h[i] ) + h[i] * h[i] + sum[i-1];
//printf("%lld %lld %lld\n",query( h[i] ), sum[i-1],dp[i]);
update( pll( -2LL*h[i], h[i]*h[i] - sum[i] + dp[i] ) );
}
//printf("\n");
printf("%lld",dp[n]);
return 0;
}
Compilation message
building.cpp: In function 'void update(std::pair<long long int, long long int>, int, int, int)':
building.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
building.cpp: In function 'long long int query(long long int, int, int, int)':
building.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
building.cpp: In function 'int main()':
building.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
building.cpp:40:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&h[i]);
~~~~~^~~~~~~~~~~~~~
building.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&sum[i]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
66296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
62968 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
62968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
