/**
* Notes during contest.
*
* ------ A ------
* In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
* that the subset of pillars shall be connected in order? First, sum all costs of
* pillars. The cost of pillars that are used will then be deducted from the total.
* Our dp formula is:
* dp[k] = min( dp[i] + (h[k] - h[i])^2 - c[k])
* = min( (dp[i] + h[i]^2) - 2h[i] * h[k] ) + (h[k]^2 - c[k])
* This looks like sth that can be solved with dynamic convex hull trick. IMO this
* is like the only way to AC this problem. Unfortunately, I don't know how to code
* one using std::set<>, nor do I know LiChao tree. Maybe I'll just head to problem
* C.
* [After contest]
* First of all, I think i should've noticed the small size of |w_i| in [S2] allows
* us to store things in a std::set<> for each value of w_i. Now, without a time
* limit, let's try LiChao tree in impl2, and perhaps the dynamic convex hull trick
* optimization in impl3 (notoriously difficult to code...).
*
* ------ B ------
* [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
* can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
* problems... I guess 60 points would be my limit.
*
* ------ C ------
* Can we score some partials here? Clearly, when Tom visits the route, only the
* last node has pigeons, so #pigeons_Tom_meets = #last_node_in_route. OK. Let V be
* the set of nodes in the route, so |V| <= v and
* #pigeons_Tom_meets = sum{ p_i : i is adjacent to at least one node in V
* or i is in V }. (Wrong, see below)
* We also know that #pigeons_Jerry_meets = p_i where i is the first node. This means
* we can solve [S1-3]. Looks like DFS + dp on tree is good enough to solve the whole
* problem!
* --------------------------------- After contest -----------------------------------
* I totally misunderstood the problem... Took me over an hour in the contest.. The
* stuff above is wrong... Full solution is a standard dfs + dp on tree in O(nv).
*
* Time Complexity 1: O(n * log(n))
* Time Complexity 2: O(n^2)
* Time Complexity 3: O(n * v)
* Implementation 2 (Full solution, LiChao Tree)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
typedef std::complex<int_t> complex_t;
const int_t INF = 0x3f3f3f3f3f3f;
const int_t H_MAX = 1e6;
inline int_t sqr(int_t k) { return k * k; }
inline int_t dot(const complex_t& c1, const complex_t& c2) {
return (std::conj(c1) * c2).real();
}
struct LiChao {
int_t max_x;
std::vector<complex_t> tree;
LiChao(int_t max) {
max_x = max;
tree.assign(3 * max_x, complex_t{0, -INF});
}
void _insert(int_t k, int_t i, int_t j, complex_t line) {
if (j - i == 1)
return;
int_t mid = (i + j) / 2;
bool mid_g = (dot(line, complex_t{mid, 1}) > dot(tree[k], complex_t{mid, 1}));
bool left_g = (dot(line, complex_t{i, 1}) >= dot(tree[k], complex_t{i, 1}));
if (mid_g)
std::swap(line, tree[k]);
if (mid_g != left_g)
_insert(2 * k, i, mid, line);
else
_insert(2 * k + 1, mid, j, line);
}
int_t _query(int_t k, int_t i, int_t j, int_t x) {
if (j - i == 1)
return -INF;
int_t mid = (i + j) / 2, val = dot(tree[k], complex_t{x, 1});
if (x < mid)
return std::max(val, _query(2 * k, i, mid, x));
else
return std::max(val, _query(2 * k + 1, mid, j, x));
}
inline void insert(complex_t line) { _insert(1, 0, max_x, line); }
inline int_t query(int_t x) { return _query(1, 0, max_x, x); }
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int_t n;
std::cin >> n;
vec h(n), cost(n);
for (int_t k = 0; k < n; k++)
std::cin >> h[k];
int_t cost_sum = 0;
for (int_t k = 0; k < n; k++) {
std::cin >> cost[k];
cost_sum += cost[k];
}
vec dp(n);
dp[0] = -cost[0];
LiChao tree(2 * H_MAX + 1);
tree.insert(complex_t{2 * h[0], -dp[0] - sqr(h[0])});
for (int_t k = 1; k < n; k++) {
// dp[k] = INF;
// for (int_t i = k - 1; i >= 0; i--)
// dp[k] = std::min(dp[k], dp[i] + sqr(h[k] - h[i]));
// dp[k] -= cost[k];
dp[k] = -tree.query(h[k]) + (sqr(h[k]) - cost[k]);
tree.insert(complex_t{2 * h[k], -dp[k] - sqr(h[k])});
}
std::cout << dp[n - 1] + cost_sum << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
94136 KB |
Output is correct |
| 2 |
Correct |
34 ms |
94156 KB |
Output is correct |
| 3 |
Correct |
43 ms |
94164 KB |
Output is correct |
| 4 |
Correct |
39 ms |
94256 KB |
Output is correct |
| 5 |
Correct |
45 ms |
94256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
97364 KB |
Output is correct |
| 2 |
Correct |
74 ms |
97356 KB |
Output is correct |
| 3 |
Correct |
80 ms |
97276 KB |
Output is correct |
| 4 |
Correct |
71 ms |
97408 KB |
Output is correct |
| 5 |
Correct |
71 ms |
97372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
94136 KB |
Output is correct |
| 2 |
Correct |
34 ms |
94156 KB |
Output is correct |
| 3 |
Correct |
43 ms |
94164 KB |
Output is correct |
| 4 |
Correct |
39 ms |
94256 KB |
Output is correct |
| 5 |
Correct |
45 ms |
94256 KB |
Output is correct |
| 6 |
Correct |
76 ms |
97364 KB |
Output is correct |
| 7 |
Correct |
74 ms |
97356 KB |
Output is correct |
| 8 |
Correct |
80 ms |
97276 KB |
Output is correct |
| 9 |
Correct |
71 ms |
97408 KB |
Output is correct |
| 10 |
Correct |
71 ms |
97372 KB |
Output is correct |
| 11 |
Correct |
79 ms |
97372 KB |
Output is correct |
| 12 |
Correct |
86 ms |
97368 KB |
Output is correct |
| 13 |
Correct |
78 ms |
97252 KB |
Output is correct |
| 14 |
Correct |
99 ms |
97368 KB |
Output is correct |
| 15 |
Correct |
72 ms |
97364 KB |
Output is correct |
| 16 |
Correct |
73 ms |
97352 KB |
Output is correct |
| 17 |
Correct |
79 ms |
97372 KB |
Output is correct |
| 18 |
Correct |
67 ms |
97368 KB |
Output is correct |
