제출 #619082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619082		jophyyjh	Building Bridges (CEOI17_building)	C++14	100 / 100	99 ms	97408 KiB

building

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

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