oj.uz

Submission #411138

# Submission time Handle Problem Language Result Execution time Memory
411138 2021-05-24T12:18:04 Z Blagojce Building Bridges (CEOI17_building) C++11
100 / 100
 108 ms 12816 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 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;
}
const ld inf = 1e18;

struct chtDynamic {  
	struct line {
		ll m, b; ld x; 
		ll val; bool isQuery; 
		line(ll _m = 0, ll _b = 0) : 
			m(_m), b(_b), val(0), x(-inf), isQuery(false) {} 
		
		ll eval(ll x) const { return m * x + b;	}
		bool parallel(const line &l) const { return m == l.m; }
		ld intersect(const line &l) const {
			return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m);
		}
		bool operator < (const line &l) const {
			if(l.isQuery) return x < l.val;
			else return m < l.m; 
		}
	};

	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); tmp.x = x;
		it = hull.erase(it); 
		return hull.insert(it, tmp);
	}

	void addLine(ll m, ll b) { 
		line l(m, b); 
		iter it = hull.lower_bound(l); 
		if(it != hull.end() && l.parallel(*it)) {
			if(it -> b < b) it = hull.erase(it); 
			else return;
		}

		it = hull.insert(it, l); 
		if(bad(it)) return (void) hull.erase(it);

		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) const { 
		if(hull.empty()) return -inf;
		line q; q.val = x, q.isQuery = 1;
		iter it = --hull.lower_bound(q);
		return it -> eval(x);
	}
} ds;



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;
	ds.addLine(2*h[0], -(dp[0] + p(h[0])-pref[0]));
	
	
	fr(i, 1, n){
		dp[i] = -ds.query(h[i]) + p(h[i]) + pref[i] - w[i];
		
		
		ds.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

*/

Compilation message

building.cpp: In constructor 'chtDynamic::line::line(ll, ll)':
building.cpp:40:6: warning: 'chtDynamic::line::val' will be initialized after [-Wreorder]
   40 |   ll val; bool isQuery;
      |      ^~~
building.cpp:39:15: warning:   'ld chtDynamic::line::x' [-Wreorder]
   39 |   ll m, b; ld x;
      |               ^
building.cpp:41:3: warning:   when initialized here [-Wreorder]
   41 |   line(ll _m = 0, ll _b = 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 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3564 KB Output is correct
2 Correct 93 ms 3576 KB Output is correct
3 Correct 94 ms 3512 KB Output is correct
4 Correct 91 ms 3396 KB Output is correct
5 Correct 90 ms 5188 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 1 ms 332 KB Output is correct
6 Correct 93 ms 3564 KB Output is correct
7 Correct 93 ms 3576 KB Output is correct
8 Correct 94 ms 3512 KB Output is correct
9 Correct 91 ms 3396 KB Output is correct
10 Correct 90 ms 5188 KB Output is correct
11 Correct 84 ms 3448 KB Output is correct
12 Correct 97 ms 3520 KB Output is correct
13 Correct 63 ms 3360 KB Output is correct
14 Correct 97 ms 3436 KB Output is correct
15 Correct 108 ms 12816 KB Output is correct
16 Correct 79 ms 5208 KB Output is correct
17 Correct 21 ms 3444 KB Output is correct
18 Correct 21 ms 3352 KB Output is correct