oj.uz

Submission #920940

# Submission time Handle Problem Language Result Execution time Memory
920940 2024-02-03T08:13:05 Z TIN Building Bridges (CEOI17_building) C++17
30 / 100
 66 ms 5836 KB 
#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 + 1, 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;
}

Compilation message

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.0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 66 ms 5836 KB Output isn't correct
7 Halted 0 ms 0 KB -