oj.uz

Submission #896196

# Submission time Handle Problem Language Result Execution time Memory
896196 2024-01-01T02:02:38 Z thunopro Building Bridges (CEOI17_building) C++14
100 / 100
 64 ms 130960 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 nw ) 
	{
		if ( l == r ) 
		{
			if ( T[id].eval(l) > nw.eval(l) ) T [id] = nw ; 
			return ; 
		}
		int mid = (l+r)/2 ; 
		if ( T[id].a > nw.a ) swap (T[id],nw) ; 
		if ( T[id].eval(mid) > nw.eval(mid) ) swap (T[id],nw) , update (right,mid+1,r,nw) ; 
		else update (left,l,mid,nw) ; 
	}
	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 34 ms 129872 KB Output is correct
2 Correct 18 ms 129704 KB Output is correct
3 Correct 18 ms 129884 KB Output is correct
4 Correct 20 ms 129740 KB Output is correct
5 Correct 18 ms 129880 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 129884 KB Output is correct
2 Correct 52 ms 130916 KB Output is correct
3 Correct 51 ms 130900 KB Output is correct
4 Correct 51 ms 130648 KB Output is correct
5 Correct 46 ms 130908 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 129872 KB Output is correct
2 Correct 18 ms 129704 KB Output is correct
3 Correct 18 ms 129884 KB Output is correct
4 Correct 20 ms 129740 KB Output is correct
5 Correct 18 ms 129880 KB Output is correct
6 Correct 52 ms 129884 KB Output is correct
7 Correct 52 ms 130916 KB Output is correct
8 Correct 51 ms 130900 KB Output is correct
9 Correct 51 ms 130648 KB Output is correct
10 Correct 46 ms 130908 KB Output is correct
11 Correct 64 ms 130900 KB Output is correct
12 Correct 59 ms 130648 KB Output is correct
13 Correct 50 ms 130936 KB Output is correct
14 Correct 64 ms 130928 KB Output is correct
15 Correct 44 ms 130636 KB Output is correct
16 Correct 44 ms 130764 KB Output is correct
17 Correct 38 ms 130760 KB Output is correct
18 Correct 40 ms 130960 KB Output is correct