제출 #920942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920942		TIN	Building Bridges (CEOI17_building)	C++17	100 / 100	44 ms	8016 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

typedef long long ll;

const int N = 1e5 + 5;
const int H = 1e6 + 5;
const ll oo = 4e18;

int n;
ll h[N], w[N], dp[N];
ll suf[N];

struct Line {
	ll a, b;

	Line() : a(0), b(oo) {}

	Line(ll a, ll b) : a(a), b(b) {}

	ll operator () (ll x) { return a * x + b; }
};

struct LiChaoTree {
	struct Node {
		Line line;
		Node *L = NULL, *R = NULL;

		Node() {}

		Node(Line line) : line(line) {}
	};

	Node *root;

	LiChaoTree() {
		root = new Node(Line());
	}

	void add(Node *node, int l, int r, Line line) {
		int m = (l + r) / 2;
		bool left = node->line(l) > line(l);
		bool mid = node->line(m) > line(m);

		if (mid) swap(line, node->line);

		if (r - l == 1) {
			return;
		} else if (left != mid) {
			if (node->L) add(node->L, l, m, line);
			else node->L = new Node(line);
		} else {
			if (node->R) add(node->R, m, r, line);
			else node->R = new Node(line);
		}
	}

	void add(Line line) {
		add(root, -H, H, line);
	}

	ll query(Node *node, int l, int r, ll x) {
		int m = (l + r) / 2;

		if (r - l == 1) {
			return node->line(x);
		} else if (x < m && node->L) {
			return min(node->line(x), query(node->L, l, m, x));
		} else if (node->R) {
			return min(node->line(x), query(node->R, m, r, x));
		} else {
			return node->line(x);
		}
	}

	ll query(ll x) {
		return query(root, -H, H, x);
	}
} LCT;

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Solve() {
	//Your Code
	cin >> n;
	for (int i = 0; i < n; i++) cin >> h[i];
	for (int i = 0; i < n; i++) cin >> w[i];
	suf[n] = 0;
	for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] + w[i];
	dp[0] = 0;
	LCT.add(Line(-2LL * h[0], h[0] * h[0] + suf[1]));
	for (int i = 1; i < n; i++) {
		dp[i] = LCT.query(h[i]) + h[i] * h[i] - suf[i];
		LCT.add(Line(-2LL * h[i], h[i] * h[i] + suf[i + 1] + dp[i]));
	}
	cout << dp[n - 1] << '\n';
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

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

building.cpp: In function 'void Task()':
building.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40