oj.uz

Submission #939063

# Submission time Handle Problem Language Result Execution time Memory
939063 2024-03-06T05:04:44 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 84 ms 20180 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
 
bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define all(x) x.begin() , x.end()
#define ff first
#define ss second
#define endl '\n'
 
const int N = 1e6 + 5 ;
const int inf = 1e16 ;
const int mod = 1e9 + 8 ;
const double eps = 1e-8 ;
 
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}
 
//code
 
int n ;
int a[N] , b[N] , pref[N] , dp[N] ;

const int q = -(1LL<<62);

struct line{
	int m , c ;
	mutable function<const line*()> S ;
	bool operator <( const line& x) const{
		if ( x.c != q ) return m < x.m ;
		const line* s = S() ;
		if (!s) return 0 ;
		int v = x.m ;
		return c - s->c < (s->m-m) * v ;
	}
};

struct cht : public multiset<line>{
	bool bad ( iterator y ){
		auto z = next(y) ;
		if ( y == begin() ){
			if ( z == end() ) return 0 ;
			return y->m == z->m && y->c <= z->c ;
		}
		auto x = prev(y) ;
		if ( z == end() ) return y->m == x->m && y->c <= x->c ;
		return (x->c - y->c)*(z->m - y->m) >= ( y->c - z->c ) * ( y->m - x->m ) ;
	}
	
	void add ( int m , int b ){
		auto y = insert({m,b}) ;
		y->S = [=] { return next(y) == end() ? 0 : &*next(y) ; } ;
		if ( bad(y) ){ erase(y) ; return ; }
		while ( next(y) != end() && bad(next(y)) ) erase(next(y)) ;
		while ( y != begin() && bad (prev(y)) ) erase(prev(y)) ;
	}
	int get ( int x ){
		auto ans = *lower_bound((line) { x , q }) ;
		return -(ans.m*x + ans.c) ;
	}
	
};

void solve(){
	
	cin >> n ;
	for ( int i = 0 ; i < n ; i ++ ) cin >> a[i] ;
	for ( int i = 0 ; i < n ; i ++ ) cin >> b[i] ;
	pref[0] = a[0] ;
	cht C ;
	C.add(2*a[0],-(dp[0]+a[0]*a[0]-pref[0])) ;
	for ( int i = 1 ; i < n ; i ++ ) pref[i] = pref[i-1] + b[i] ;
	for ( int i = 1 ; i < n ; i ++ ){
		dp[i] = C.get(a[i]) + a[i]*a[i]+pref[i-1] ;
		C.add(2*a[i],-(a[i]*a[i]+dp[i]-pref[i])) ;
	}
	cout << dp[n-1] ;
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

building.cpp: In function 'void fopn(std::string)':
building.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10844 KB Output is correct
2 Correct 53 ms 10960 KB Output is correct
3 Correct 53 ms 10996 KB Output is correct
4 Correct 45 ms 10920 KB Output is correct
5 Correct 51 ms 12636 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 52 ms 10844 KB Output is correct
7 Correct 53 ms 10960 KB Output is correct
8 Correct 53 ms 10996 KB Output is correct
9 Correct 45 ms 10920 KB Output is correct
10 Correct 51 ms 12636 KB Output is correct
11 Correct 45 ms 10840 KB Output is correct
12 Correct 52 ms 10768 KB Output is correct
13 Correct 30 ms 10844 KB Output is correct
14 Correct 51 ms 10948 KB Output is correct
15 Correct 84 ms 20180 KB Output is correct
16 Correct 51 ms 12732 KB Output is correct
17 Correct 18 ms 10840 KB Output is correct
18 Correct 18 ms 10840 KB Output is correct