oj.uz

Submission #411140

# Submission time Handle Problem Language Result Execution time Memory
411140 2021-05-24T12:22:09 Z Blagojce Building Bridges (CEOI17_building) C++11
100 / 100
 185 ms 12748 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 2e5+5;

int n;
ll h[mxn];
ll w[mxn];

ll dp[mxn];

ll pref[mxn];

ll p(ll a){
	return a*a;
}


struct line{
	ll m, b;
	ld x;
	ll val;
	bool query;

	line(ll m1, ll b1, ld x1, bool q1){
		m = m1, b = b1, x = x1, query = q1;
	}
	bool operator <(const line &l) const{
		if(l.query) return x < l.val;
		else return m < l.m;
	}
	bool parallel(const line &l) const{
		return m == l.m;
	}
	ld intersect(const line &l) const{
		return 1.0*(l.b-b)/(m-l.m);
	}
	ll eval(ll x) const{
		return m*x + b;
	}
	
	
};
set<line> hull;
typedef set<line> :: iterator iter;
bool cPrev(iter it){
	return it != hull.begin();
}
bool cNext(iter it){
	return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
	return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
	return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}

iter update(iter it){
	if(!cPrev(it)) return it;
	ld x = it->intersect(*prev(it));
	line tmp(it->m, it->b, x, false);
	hull.erase(it);
	hull.insert(tmp);
	return hull.find(tmp);
}


void addLine(ll m, ll b){
	line l(m, b, -inf, false);
	iter it = hull.lower_bound(l);
	if(it != hull.end() && l.parallel(*it)){
		if(it->b < b) it = hull.erase(it);
		else return;
	}
	hull.insert(l);
	it = hull.find(l);
	
	if(bad(it)){
		hull.erase(it);
		return;
	}
	while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
	while(cNext(it) && bad(next(it))) hull.erase(next(it));
	
	it = update(it);
	if(cPrev(it)) update(prev(it));
	if(cNext(it)) update(next(it));
}
ll query(ll x){
	if(hull.empty()) return -inf;
	line q(0, 0, 0, true);
	q.val = x;
	iter it = --hull.lower_bound(q);
	return it->eval(x);
}



void solve(){
	cin >> n;
	fr(i, 0, n){
		cin >> h[i];
	}
	fr(i, 0, n){
		cin >> w[i];
	}
	pref[0] = w[0];
	fr(i, 1, n){
		pref[i] = pref[i-1]+w[i];
	}
	
	dp[0] = 0;
	addLine(2*h[0], -(dp[0] + p(h[0])-pref[0]));
	
	
	fr(i, 1, n){
		dp[i] = -query(h[i]) + p(h[i]) + pref[i] - w[i];
		
		
		addLine(2*h[i], -(dp[i] + p(h[i]) - pref[i]));
		
	}
	cout<<dp[n-1]<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();

}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0

*/

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3532 KB Output is correct
2 Correct 120 ms 3508 KB Output is correct
3 Correct 120 ms 3524 KB Output is correct
4 Correct 114 ms 3360 KB Output is correct
5 Correct 139 ms 5304 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 123 ms 3532 KB Output is correct
7 Correct 120 ms 3508 KB Output is correct
8 Correct 120 ms 3524 KB Output is correct
9 Correct 114 ms 3360 KB Output is correct
10 Correct 139 ms 5304 KB Output is correct
11 Correct 103 ms 3456 KB Output is correct
12 Correct 127 ms 3544 KB Output is correct
13 Correct 76 ms 3344 KB Output is correct
14 Correct 119 ms 3544 KB Output is correct
15 Correct 185 ms 12748 KB Output is correct
16 Correct 145 ms 5208 KB Output is correct
17 Correct 22 ms 3404 KB Output is correct
18 Correct 21 ms 3396 KB Output is correct