oj.uz

Submission #395622

# Submission time Handle Problem Language Result Execution time Memory
395622 2021-04-28T17:11:14 Z hltk Building Bridges (CEOI17_building) C++17
100 / 100
 103 ms 7500 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 2 ms 972 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7268 KB Output is correct
2 Correct 91 ms 7344 KB Output is correct
3 Correct 90 ms 7296 KB Output is correct
4 Correct 82 ms 7372 KB Output is correct
5 Correct 54 ms 5648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 91 ms 7268 KB Output is correct
7 Correct 91 ms 7344 KB Output is correct
8 Correct 90 ms 7296 KB Output is correct
9 Correct 82 ms 7372 KB Output is correct
10 Correct 54 ms 5648 KB Output is correct
11 Correct 90 ms 7472 KB Output is correct
12 Correct 103 ms 7364 KB Output is correct
13 Correct 98 ms 5740 KB Output is correct
14 Correct 87 ms 7500 KB Output is correct
15 Correct 56 ms 7268 KB Output is correct
16 Correct 54 ms 5676 KB Output is correct
17 Correct 51 ms 4348 KB Output is correct
18 Correct 51 ms 4144 KB Output is correct