oj.uz

Submission #166602

# Submission time Handle Problem Language Result Execution time Memory
166602 2019-12-03T02:31:33 Z thiago4532 Building Bridges (CEOI17_building) C++17
0 / 100
 307 ms 3536 KB 
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], pref[maxn], w[maxn];
int n, dp[maxn];

struct line {
	int a, b;

	line(int a, int b): a(a), b(b) {

	}

	bool operator<(line const& l) const {
		return a < l.a;
	}
};

template<typename Arg>
bool bad(Arg&& l1, Arg&& l2, Arg&& l3) {
	return (l2.a - l1.a)*(l3.b - l1.b) <= (l3.a -  l1.a)*(l2.b - l1.b);
}

set<line> lines;

void add(line const& l) {
	lines.insert(l);

	while(lines.size() > 2) {
		auto it1 = lines.find(l);
		if(it1 == lines.begin()) break;
		it1--;
		if(it1 == lines.begin()) break;
		auto it2 = it1;
		it1--;
		if(it1 == lines.begin()) break;
		auto it3 = it1;
		it1--;

		if ( bad(*it3, *it2, *it1) )
			lines.erase(it2);
		else
			break;
	}

	while(lines.size() > 2) {
		auto it1 = lines.find(l);
		it1++;
		if(it1 == lines.end()) break;
		auto it2 = it1;
		it1++;
		if(it1 == lines.end()) break;
		auto it3 = it1;
		it1++;
		if(it1 == lines.end()) break;

		if ( bad(*it1, *it2, *it3) )
			lines.erase(it2);
		else
			break;
	}
}

inline int f(line const& l, int x) {
	return l.a*x + l.b;
}

int query(int x) {
	int res=0x3f3f3f3f3f3f3f3f;
	for(auto& e : lines) {
		// cout << f(e, x) << " ";
		res = min(res, f(e,x));
	}
	// cout << "\n";
	return res;
}


int32_t main() {
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> h[i];

	for(int i=1;i<=n;i++)
		cin >> w[i], pref[i] = pref[i-1] + w[i];

	dp[1] = 0;
	add({-2*h[1], h[1]*h[1] + dp[1] - pref[1]});

	for(int i=2;i<=n;i++) {
		// dp[i] = 0x3f3f3f3f3f3f3f3f;

		// for(int j=1;j<i;j++) {
		// 	dp[i] = min(dp[i], dp[j] - pref[j] + h[j]*h[j] - 2*h[j] * h[i]);
		// }

		dp[i] = query(h[i]);

		dp[i] += h[i]*h[i] + pref[i-1];
		add({-2*h[i], h[i]*h[i] + dp[i] - pref[i]});
	}
	cout << dp[n] << "\n";
	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 3536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -