제출 #395904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395904		hltk	Building Bridges (CEOI17_building)	C++17	100 / 100	165 ms	7904 KiB

building

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40