Submission #395622

#	Time	Username	Problem	Language	Result	Execution time	Memory
395622		hltk	Building Bridges (CEOI17_building)	C++17	100 / 100	103 ms	7500 KiB

building

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define forn(i, n) for (int i = 0; i < (n); ++i)

#define MAXT (1 << 17)

struct L {
	long m = 0, c = 1e18;
	long operator()(long x) { return x * m + c; }
} t[MAXT * 2];
int x[MAXT];

void add_line(L cn, int s = 1, int l = 0, int r = MAXT) {
	if (r - l == 1) {
		t[s] = t[s](x[l]) < cn(x[l]) ? t[s] : cn;
	} else {
		int m = (l + r) / 2;
		bool cl = cn(x[l]) < t[s](x[l]);
		bool cm = cn(x[m]) < t[s](x[m]);
		if (cm) swap(cn, t[s]);
		cl != cm ? add_line(cn, s * 2, l, m) : add_line(cn, s * 2 + 1, m, r);
	}
}

long get_min(int k, int s = 1, int l = 0, int r = MAXT) {
	if (r - l == 1) {
		return t[s](x[k]);
	} else {
		long cur = t[s](x[k]);
		int m = (l + r) / 2;
		return min(cur, k < m ? get_min(k, s * 2, l, m) : get_min(k, s * 2 + 1, m, r));
	}
}

#define MAXN 100000

int n, h[MAXN], w[MAXN], p[MAXN], pr[MAXN];
long dp[MAXN];

int main() {
	scanf("%d", &n);
	forn (i, n) scanf("%d", h + i);
	forn (i, n) scanf("%d", w + i);

	long wsum = 0;
	forn (i, n) wsum += w[i];

	// dp[i] =
	//       = min_{j < i} dp[j] + (h[j] - h[i]) ^ 2 + w[i]
	//       = min_{j < i} dp[j] + h[j] ^ 2 - 2h[j]h[i] + h[i] ^ 2 + w[i]
	//       f_j(x) := h[j] ^ 2 - 2h[j]x + dp[j]
	//       = h[i] ^ 2 + w[i] + min_{j < i} f_j(h[i])

	memset(x, 0x3f, sizeof(x));
	forn (i, n) x[i] = h[i];
	forn (i, n) p[i] = i;
	sort(p, p + n, [&](int i, int j) {
		return x[i] < x[j];
	});
	forn (i, n) pr[p[i]] = i;
	sort(x, x + n);

	add_line({-2l * h[0], 1l * h[0] * h[0] - w[0]});

	for (int i = 1; i < n; ++i) {
		dp[i] = 1l * h[i] * h[i] - w[i] + get_min(pr[i]);
		add_line({-2l * h[i], 1l * h[i] * h[i] + dp[i]});
	}

	printf("%ld\n", dp[n - 1] + wsum);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:45:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  forn (i, n) scanf("%d", h + i);
      |              ~~~~~^~~~~~~~~~~~~
building.cpp:46:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  forn (i, n) scanf("%d", w + i);
      |              ~~~~~^~~~~~~~~~~~~

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