oj.uz

Submission #45956

# Submission time Handle Problem Language Result Execution time Memory
45956 2018-04-16T14:44:43 Z sorry_Benq Building Bridges (CEOI17_building) C++17
100 / 100
 123 ms 18292 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

int w[100005];
ll h[100005];
ll dp[100005];
ll res = 0;

bool Q;
struct Line {
	mutable ll k, m, p; // slope, y-intercept, last optimal x
	bool operator<(const Line& o) const {
		return Q ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> { 
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
	    if (b < 0) a *= -1, b *= -1;
	    if (a >= 0) return a/b;
	    return -((-a+b-1)/b);
	}
	
	// updates x->p, determines if y is unneeded
	bool isect(iterator x, iterator y) { 
		if (y == end()) { x->p = inf; return 0; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}
	
	ll query(ll x) { // gives max value
		assert(!empty());
		Q = 1; auto l = *lb({0,0,x}); Q = 0;
		return l.k * x + l.m;
	}
};

int main(){
	LineContainer L;
	int N; cin >> N;
	for (int i = 0; i < N; i++){
		cin >> h[i];
	}
	for (int i = 0; i < N; i++){
		cin >> w[i];
		res += w[i];
		w[i] = -w[i];
	}
	dp[0] = w[0];
	L.add(2*h[0], -h[0]*h[0] - dp[0]);
	for (int i = 1; i < N; i++){
		dp[i] = h[i]*h[i] + w[i] - L.query(h[i]);
		L.add(2*h[i], -h[i]*h[i] - dp[i]);
	}
	cout << res + dp[N - 1] << endl;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2524 KB Output is correct
2 Correct 102 ms 3452 KB Output is correct
3 Correct 99 ms 4624 KB Output is correct
4 Correct 105 ms 5624 KB Output is correct
5 Correct 93 ms 7716 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 432 KB Output is correct
6 Correct 106 ms 2524 KB Output is correct
7 Correct 102 ms 3452 KB Output is correct
8 Correct 99 ms 4624 KB Output is correct
9 Correct 105 ms 5624 KB Output is correct
10 Correct 93 ms 7716 KB Output is correct
11 Correct 113 ms 7792 KB Output is correct
12 Correct 104 ms 8860 KB Output is correct
13 Correct 94 ms 9916 KB Output is correct
14 Correct 119 ms 11212 KB Output is correct
15 Correct 123 ms 18292 KB Output is correct
16 Correct 98 ms 18292 KB Output is correct
17 Correct 79 ms 18292 KB Output is correct
18 Correct 79 ms 18292 KB Output is correct