Submission #1182168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182168		kanhngocieu123	Building Bridges (CEOI17_building)	C++20	0 / 100	7 ms	15940 KiB

building

/* Author : Phan Thanh Nhan, ITK22, NBK High School for Gifted Student */

#include <bits/stdc++.h>

#define TASK "CEOI17_building"
#define ll long long
#define fi first
#define sc second
#define ii pair <int, int>  
#define iii pair <int, ii>
#define int ll  

using namespace std;

const int MAXN = 1e6;
const int INF = 2e9;
const ll LINF = 1e18;

struct line {
	int a, b;
	
	line () {
		a = 0;
		b = 0;
	}

	line(int valA, int valB) {
		a = valA;
		b = valB;
	}

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

	int slope() {
		return a; 
	}
};

vector <line> st;

int pref[MAXN + 5], n, h[MAXN + 5], w[MAXN + 5], dp[MAXN + 5];

void update(int l, int r, line newLine) {
	if (l > r) return;
	int mid = (l + r) >> 1;

	if (l == r) {
		st[mid] = (st[mid].cal(l) < newLine.cal(l) ? st[mid] : newLine);
		return;
	}

	if (newLine.cal(mid) < st[mid].cal(mid)) swap(newLine, st[mid]);
	if (newLine.slope() > st[mid].slope()) update(l, mid - 1, newLine);
	if (newLine.slope() < st[mid].slope()) update(mid + 1, r, newLine);
}

int get(int l, int r, int idx) {
	int mid = (l + r) >> 1;
	int ans = st[mid].cal(idx);
	if (idx == mid) return ans;
	if (idx > mid) return min(ans, get(mid + 1, r, idx));
	return min(ans, get(l, mid - 1, idx));
}

int fiCost(int i) {
	return -2 * h[i];
}

int scCost(int i) {
	return dp[i] + h[i] * h[i] - pref[i];
}


void Bindu() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		pref[i] = pref[i - 1] + w[i];
	}

	st.resize(MAXN + 2, line(0, LINF));
	update(0, MAXN, line(fiCost(1), scCost(1)));

	dp[1] = 0;

	for (int i = 2; i <= n; i++) {
		dp[i] = get(0, MAXN, h[i]) + h[i] * h[i] + pref[i - 1];
		update(0, MAXN, line(fiCost(i), scCost(i)));
	}

	cout << dp[n];
}

signed main() {
	#ifndef ONLINE_JUDGE
	freopen(TASK".inp", "r", stdin);
	freopen(TASK".out", "w", stdout);
	#endif
	cin.tie(0)->sync_with_stdio(false);
	Bindu();
	return 0;
}

/* Comment

	Coming soon...	
*/

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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