Submission #47426

#	Time	Username	Problem	Language	Result	Execution time	Memory
47426		bugmenot111	Building Bridges (CEOI17_building)	C++17	100 / 100	170 ms	78820 KiB

building

#include <cstdio>
#include <numeric>
#include <algorithm>
#define INF (1LL << 62)
#define MAXN 1000001
typedef long long i64;
struct line {
	i64 a, b;
	i64 f(int x) {
		return 1LL * x * a + b;
	}
	void swap(line& l) {
		std::swap(a, l.a);
		std::swap(b, l.b);
	}
	line () {
		a = 0;
		b = INF;
	}
	line (i64 a1, i64 b1) {
		a = a1;
		b = b1;
	}
};
line t[4 * MAXN];
i64 dp[MAXN];
i64 p[MAXN];
int h[MAXN];
void add_line(line nw, int v = 1, int l = 0, int r = MAXN) {
	int m = (l + r) / 2;
	bool lef = nw.f(l) < t[v].f(l);
	bool mid = nw.f(m) < t[v].f(m);
	if(mid) nw.swap(t[v]);
	if(r - l == 1) return;
	if(lef != mid) add_line(nw, 2 * v, l, m); else add_line(nw, 2 * v + 1, m, r);
}
i64 get(int x, int v = 1, int l = 0, int r = MAXN) {
	int m = (l + r) / 2;
	if(r - l == 1) return t[v].f(x);
	else if(x < m) return std::min(t[v].f(x), get(x, 2 * v, l, m));
	else return std::min(t[v].f(x), get(x, 2 * v + 1, m, r));
}
int main(void) {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &h[i]);
	for(int i = 0; i < n; i++)
		scanf("%lld", &p[i]);
	for(int i = 1; i < n; i++) p[i] += p[i - 1];
	add_line(line(-2LL * h[0], 1LL * h[0] * h[0] - p[0]));
	for(int i = 1; i < n; i++) {
		i64 x = get(h[i]);
		dp[i] = p[i - 1] + 1LL * h[i] * h[i] + x;
		add_line(line(-2LL * h[i], dp[i] + 1LL * h[i] * h[i] - p[i]));
	}
	printf("%lld\n", dp[n - 1]);
	return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &h[i]);
   ~~~~~^~~~~~~~~~~~~
building.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i]);
   ~~~~~^~~~~~~~~~~~~~~

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