Submission #920920

#	Time	Username	Problem	Language	Result	Execution time	Memory
920920		TIN	Building Bridges (CEOI17_building)	C++17	100 / 100	52 ms	66896 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define FNAME "BRIDGEPOL"

#define int long long

const int N = 1e5 + 5;
const int C = 1e6 + 5;
const int oo = 1e18;

struct Line {
	int a,b;
	
	Line(int _a = 0, int _b = oo) : a(_a), b(_b) {}

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

int n, h[N], w[N], dp[N];
Line LCT[4 * C];

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 update(int id, int l, int r, Line d) {
	int mid = (l + r) >> 1;
	int idL = id * 2, idR = id * 2 + 1;
	bool L = d(l) < LCT[id](l);
	bool M = d(mid) < LCT[id](mid);
	if (M) swap(LCT[id], d);
	if (l == r) return;
	if (L ^ M) update(idL, l, mid, d);
	else update(idR, mid + 1, r, d);
}

int query(int id, int l, int r, int x) {
	if (l == r) return LCT[id](x);
	int mid = (l + r) >> 1;
	int idL = id * 2, idR = id * 2 + 1;
	if (x < mid) return min(LCT[id](x), query(idL, l, mid, x));
	else return min(LCT[id](x), query(idR, mid + 1, r, x));
}

void Solve() {
	//Your Code
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	w[0] = 0;
	for (int i = 1; i <= n; i++) cin >> w[i], w[i] += w[i - 1];

	dp[1] = 0;
	update(1, 1, C, Line(-2 * h[1], h[1] * h[1] - w[1] + dp[1]));
	for (int i = 2; i <= n; i++) {
		dp[i] = h[i] * h[i] + w[i - 1] + query(1, 1, C, h[i]);
		update(1, 1, C, Line(-2 * h[i], h[i] * h[i] - w[i] + dp[i]));
	}

	cout << dp[n] << '\n';
}

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

Compilation message (stderr)

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

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