oj.uz

Submission #395904

# Submission time Handle Problem Language Result Execution time Memory
395904 2021-04-29T07:23:21 Z hltk Building Bridges (CEOI17_building) C++17
100 / 100
 165 ms 7904 KB 
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <tuple>
#include <vector>
using namespace std;

#define forn(i, n) for (int i = 0; i < (n); ++i)
#define MAXN 100000

struct Line {
	long m, c;
	long operator()(long x) { return m * x + c; }
	bool operator<(Line a) const { return m != a.m ? m < a.m : a.c < c; }
};

long intersect(Line a, Line b) {
	long num = b.c - a.c, dem = a.m - b.m;
	return num / dem - ((num ^ dem) < 0 && num % dem);
}

const long INF = 1e18;

struct hull {
	vector<pair<long, Line>> lines;
	vector<Line> all;
	hull(Line l) : lines{{-INF, l}}, all{l} {}
	hull(hull &a, hull &b) {
		all.resize(a.size() + b.size());
		merge(a.all.begin(), a.all.end(), b.all.begin(), b.all.end(), all.begin());
		lines.reserve(all.size());
		lines.push_back({-INF, *all.begin()});
		for (int i = 1; i < (int) all.size(); ++i) {
			auto l = all[i];
			if (lines.back().second.m == l.m) continue;
			while (lines.size() >= 2) {
				auto al = lines[lines.size() - 2].second;
				auto bl = lines[lines.size() - 1].second;
				if (intersect(bl, l) <= intersect(al, bl)) {
					lines.pop_back();
				} else break;
			}
			lines.emplace_back(intersect(lines.back().second, l), l);
		}
	}
	long query(long x) {
		return prev(lower_bound(lines.begin(), lines.end(), pair{x, Line{}}, [&](auto a, auto b) {
			return a.first < b.first;
		}))->second(x);
	}
	size_t size() { return all.size(); }
};

struct hulls {
	vector<hull> h;
	void add_line(Line x) {
		x.c = -x.c;
		x.m = -x.m;
		h.emplace_back(x);
		while (h.size() >= 2 && h[h.size() - 2].size() == h[h.size() - 1].size()) {
			auto a = h[h.size() - 2];
			auto b = h[h.size() - 1];
			h.pop_back();
			h.pop_back();
			h.emplace_back(a, b);
		}
	}
	long query(long x) {
		long ret = -INF;
		for (auto &u : h)
			ret = max(ret, u.query(x));
		return -ret;
	}
} cht;

int n, h[MAXN], w[MAXN];
long dp[MAXN];

int main() {
	scanf("%d", &n);
	forn (i, n) scanf("%d", h + i);
	forn (i, n) scanf("%d", w + i);

	long wsum = 0;
	forn (i, n) wsum += w[i];

	// dp[i] =
	//       = min_{j < i} dp[j] + (h[j] - h[i]) ^ 2 + w[i]
	//       = min_{j < i} dp[j] + h[j] ^ 2 - 2h[j]h[i] + h[i] ^ 2 + w[i]
	//       f_j(x) := h[j] ^ 2 - 2h[j]x + dp[j]
	//       = h[i] ^ 2 + w[i] + min_{j < i} f_j(h[i])

	cht.add_line({-2l * h[0], 1l * h[0] * h[0] - w[0]});

	for (int i = 1; i < n; ++i) {
		dp[i] = 1l * h[i] * h[i] - w[i] + cht.query(h[i]);
		cht.add_line({-2l * h[i], 1l * h[i] * h[i] + dp[i]});
	}

	printf("%ld\n", dp[n - 1] + wsum);
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:81:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  forn (i, n) scanf("%d", h + i);
      |              ~~~~~^~~~~~~~~~~~~
building.cpp:82:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  forn (i, n) scanf("%d", w + i);
      |              ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 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 154 ms 4684 KB Output is correct
2 Correct 150 ms 5764 KB Output is correct
3 Correct 153 ms 5800 KB Output is correct
4 Correct 138 ms 5456 KB Output is correct
5 Correct 125 ms 6688 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 154 ms 4684 KB Output is correct
7 Correct 150 ms 5764 KB Output is correct
8 Correct 153 ms 5800 KB Output is correct
9 Correct 138 ms 5456 KB Output is correct
10 Correct 125 ms 6688 KB Output is correct
11 Correct 165 ms 6044 KB Output is correct
12 Correct 161 ms 5596 KB Output is correct
13 Correct 116 ms 5560 KB Output is correct
14 Correct 163 ms 5904 KB Output is correct
15 Correct 114 ms 7904 KB Output is correct
16 Correct 127 ms 6776 KB Output is correct
17 Correct 64 ms 6988 KB Output is correct
18 Correct 71 ms 6972 KB Output is correct