oj.uz

Submission #536567

# Submission time Handle Problem Language Result Execution time Memory
536567 2022-03-13T14:27:37 Z Asymmetry Building Bridges (CEOI17_building) C++17
100 / 100
 56 ms 35276 KB 
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct LiChao {
	struct node {
		int a;
		long long b;
		// ax + b
	};
	
	long long val(node p, int x) {
		return (long long)p.a * x + p.b;
	}
	
	int com;
	vector<node> st;
	LiChao(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(com << 1);
		for (int i = 0; i < com << 1; ++i) {
			st[i].b = 1e18;
		}
	}
	
	void ins(int x, int l, int r, node p) {
		int mid = (l + r) / 2;
		if (val(st[x], l) <= val(p, l)) {
			if (val(st[x], r) <= val(p, r)) {
				return;
			}
			if (val(st[x], mid) <= val(p, mid)) {
				ins(x * 2 + 1, mid + 1, r, p);
			}
			else {
				swap(st[x], p);
				ins(x * 2, l, mid, p);
			}
		}
		else {
			if (val(st[x], r) >= val(p, r)) {
				swap(st[x], p);
				return;
			}
			if (val(st[x], mid) <= val(p, mid)) {
				ins(x * 2, l, mid, p);
			}
			else {
				swap(st[x], p);
				ins(x * 2 + 1, mid + 1, r, p);
			}
		}
	}
	
	void dodaj(int a, long long b) {
		ins(1, 1, com, {a, b});
	}
	
	long long wynik(int x) {
		long long ret = 1e18;
		int y = x + com - 1;
		while (y) {
			ret = min(ret, (long long)st[y].a * x + st[y].b);
			y >>= 1;
		}
		return ret;
	}
};

const int N = 101'000;
int n;
int h[N];
long long pref[N];

int main() {
	int mx = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &h[i]);
		++h[i];
		mx = max(mx, h[i]);
	}
	LiChao dp(mx);
	long long odp;
	scanf("%lld", &pref[1]);
	dp.dodaj(-2 * h[1], (long long)h[1] * h[1] - pref[1]);
	
	for (int i = 2; i <= n; ++i) {
		scanf("%lld", &pref[i]);
		pref[i] += pref[i - 1];
		odp = (long long)h[i] * h[i] + pref[i - 1] + dp.wynik(h[i]);
		dp.dodaj(-2 * h[i], odp - pref[i] + (long long)h[i] * h[i]);
	}
	printf("%lld\n", odp);
	return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%lld", &pref[1]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
building.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%lld", &pref[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6600 KB Output is correct
2 Correct 36 ms 6532 KB Output is correct
3 Correct 35 ms 6524 KB Output is correct
4 Correct 35 ms 6500 KB Output is correct
5 Correct 33 ms 10524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 37 ms 6600 KB Output is correct
7 Correct 36 ms 6532 KB Output is correct
8 Correct 35 ms 6524 KB Output is correct
9 Correct 35 ms 6500 KB Output is correct
10 Correct 33 ms 10524 KB Output is correct
11 Correct 36 ms 6776 KB Output is correct
12 Correct 56 ms 6572 KB Output is correct
13 Correct 27 ms 2708 KB Output is correct
14 Correct 38 ms 6720 KB Output is correct
15 Correct 36 ms 10444 KB Output is correct
16 Correct 33 ms 10616 KB Output is correct
17 Correct 43 ms 35276 KB Output is correct
18 Correct 21 ms 2480 KB Output is correct