제출 #536567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536567		Asymmetry	Building Bridges (CEOI17_building)	C++17	100 / 100	56 ms	35276 KiB

building

//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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40