oj.uz

Submission #896197

# Submission time Handle Problem Language Result Execution time Memory
896197 2024-01-01T02:03:41 Z thunopro Building Bridges (CEOI17_building) C++14
100 / 100
 59 ms 130100 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long 
#define maxn 200009 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1 
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1  
 
const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 
 
typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<ll> vl ; 
typedef vector<pii> vii ; 
 
void add ( int &a , int b ) 
{
	a += b ;
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}
 
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 
 
void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}
 
int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}
 
int n ; 
ll dp [maxn] ; 
int h [maxn] , w [maxn] ; 
ll sw [maxn] ; 
 
ll sqr ( int x ) 
{
	return 1ll*x*x ; 
}
 
struct line {
	int a ; ll b ; 
	line () { a = 0 , b = 1e18 ; } ; 
	line ( int _a , ll _b ) 
	{
		a = _a , b = _b ; 
	}
	ll eval ( int x ) 
	{
		return 1ll*x*a+b ; 
	} 
};
 
const int N = 2e6 ; 
const int maxN = 2e6+2 ; 
struct lichao {
	line T [maxN*4] ; 
	void update ( int id , int l , int r , line L ) 
	{
		if ( l == r ) 
		{
			if ( T[id].eval(l) > L.eval(l) ) T [id] = L ; 
			return ; 
		}
		int mid = (l+r)/2 ; 
		if ( T[id].a > L.a ) swap (T[id],L) ; 
		if ( T[id].eval(mid)>L.eval(mid)) swap (T[id],L) , update (right,mid+1,r,L) ; 
		else update (left,l,mid,L) ; 
	}
	ll get ( int id , int l , int r , int x ) 
	{
		if ( l == r ) return T [id].eval(x) ; 
		int mid = (l+r)/2 ; 
		if ( x <= mid ) return min(T[id].eval(x),get(left,l,mid,x)) ;
		else return min (T[id].eval(x),get(right,mid+1,r,x)) ; 
	}	
	void update ( line L )
	{
		update (1,1,N,L) ; 
	}
	ll get ( int x ) 
	{
		return get (1,1,N,x) ; 
	}
}T;
void add_lichao ( int i ) 
{
	line L = {-h[i],dp[i]+sqr(h[i])-sw[i]} ; 
	T.update (L) ; 
}
int main () 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	cin >> n ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> h [i] ;
	for ( int i = 1 ; i <= n ; i ++ ) {
		cin >> w [i] ; 
		sw [i] = sw [i-1] + w [i] ; 
	}
	
	dp [1] = 0 ; 
	add_lichao (1) ; 
	
	for ( int i = 2 ; i <= n ; i ++ ) 
	{
		dp [i] = T.get(2*h[i]) + sqr (h[i]) + sw [i-1] ; 
		add_lichao (i) ; 
	}
	
	cout << dp [n] ; 
}
 
// range , error , check special , ... 
// find key , find key 
//'-std=c++11' stay hard 
// there is no tomorrow

Compilation message

building.cpp: In function 'void rf()':
building.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 129708 KB Output is correct
2 Correct 18 ms 129884 KB Output is correct
3 Correct 20 ms 129880 KB Output is correct
4 Correct 18 ms 129884 KB Output is correct
5 Correct 19 ms 129772 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 130100 KB Output is correct
2 Correct 51 ms 129876 KB Output is correct
3 Correct 52 ms 129876 KB Output is correct
4 Correct 48 ms 129880 KB Output is correct
5 Correct 45 ms 129876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 129708 KB Output is correct
2 Correct 18 ms 129884 KB Output is correct
3 Correct 20 ms 129880 KB Output is correct
4 Correct 18 ms 129884 KB Output is correct
5 Correct 19 ms 129772 KB Output is correct
6 Correct 53 ms 130100 KB Output is correct
7 Correct 51 ms 129876 KB Output is correct
8 Correct 52 ms 129876 KB Output is correct
9 Correct 48 ms 129880 KB Output is correct
10 Correct 45 ms 129876 KB Output is correct
11 Correct 58 ms 129884 KB Output is correct
12 Correct 57 ms 129884 KB Output is correct
13 Correct 50 ms 129892 KB Output is correct
14 Correct 59 ms 129884 KB Output is correct
15 Correct 50 ms 129880 KB Output is correct
16 Correct 44 ms 129884 KB Output is correct
17 Correct 38 ms 129884 KB Output is correct
18 Correct 45 ms 129876 KB Output is correct