Submission #619066

#	Time	Username	Problem	Language	Result	Execution time	Memory
619066		jophyyjh	Building Bridges (CEOI17_building)	C++14	30 / 100	12 ms	352 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. I'll make
 * a LiChao Tree. IMO this is like the only way to AC this problem.
 * 
 * ------ 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?
 * 
 * Time Complexity 1: O(n^2)
 * Time Complexity 2: O(n^2)
 * Time Complexity 3: O()
 * Implementation 0.5       (testing, only solves [S1])
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
const int_t INF = 0x3f3f3f3f3f3f;
 
inline int_t sqr(int_t k)   { return k * k; }
 
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t n, cost_sum = 0;;
    std::cin >> n;
    if (n > 1000) {
        std::cout << "bye\n";
        return 0;
    }
    vec heights(n), costs(n);
    for (int_t k = 0; k < n; k++)
        std::cin >> heights[k];
    for (int_t k = 0; k < n; k++) {
        std::cin >> costs[k];
        cost_sum += costs[k];
    }
 
    
    vec dp(n);
    dp[0] = -costs[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(heights[k] - heights[i]));
        dp[k] -= costs[k];
    }
    std::cout << dp[n - 1] + cost_sum << '\n';
}

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