oj.uz

Submission #920920

# Submission time Handle Problem Language Result Execution time Memory
920920 2024-02-03T07:46:00 Z TIN Building Bridges (CEOI17_building) C++17
100 / 100
 52 ms 66896 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 64092 KB Output is correct
2 Correct 12 ms 64092 KB Output is correct
3 Correct 11 ms 64252 KB Output is correct
4 Correct 11 ms 64132 KB Output is correct
5 Correct 11 ms 64092 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 66180 KB Output is correct
2 Correct 45 ms 66384 KB Output is correct
3 Correct 45 ms 66428 KB Output is correct
4 Correct 42 ms 66208 KB Output is correct
5 Correct 40 ms 66140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 64092 KB Output is correct
2 Correct 12 ms 64092 KB Output is correct
3 Correct 11 ms 64252 KB Output is correct
4 Correct 11 ms 64132 KB Output is correct
5 Correct 11 ms 64092 KB Output is correct
6 Correct 44 ms 66180 KB Output is correct
7 Correct 45 ms 66384 KB Output is correct
8 Correct 45 ms 66428 KB Output is correct
9 Correct 42 ms 66208 KB Output is correct
10 Correct 40 ms 66140 KB Output is correct
11 Correct 52 ms 66896 KB Output is correct
12 Correct 49 ms 66408 KB Output is correct
13 Correct 39 ms 66396 KB Output is correct
14 Correct 49 ms 66504 KB Output is correct
15 Correct 39 ms 66152 KB Output is correct
16 Correct 40 ms 66192 KB Output is correct
17 Correct 33 ms 66396 KB Output is correct
18 Correct 38 ms 66396 KB Output is correct