Submission #123828

#	Time	Username	Problem	Language	Result	Execution time	Memory
123828		FutymyClone	Building Bridges (CEOI17_building)	C++14	0 / 100	95 ms	2936 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long inf = 1LL << 62;

int n, h[N], w[N];
long long dp[N], f[N];

class ConvexHullTrick {
    struct line {
        long long m, b, value;
        double xlo;
        bool is_query, query_max;

        line(long long m, long long b, long long v, bool is_query, bool query_max)
            : m(m), b(b), value(v), xlo(-std::numeric_limits<double>::max()),
            is_query(is_query), query_max(query_max) {}

        double intersect(const line &l) const {
            if (m == l.m) return std::numeric_limits<double>::max();
            return (double)(l.b - b)/(m - l.m);
        }

        bool operator<(const line &l) const {
            if (l.is_query) return query_max ? (xlo < l.value) : (l.value < xlo);
            return m < l.m;
        }
    };

    std::set<line> hull;
    bool query_max;

    typedef std::set<line>::iterator hulliter;

    bool has_prev(hulliter it) const {
        return it != hull.begin();
    }

    bool has_next(hulliter it) const {
        return (it != hull.end()) && (++it != hull.end());
    }

    bool irrelevant(hulliter it) const {
        if (!has_prev(it) || !has_next(it)) return false;
        hulliter prev = it, next = it;
        --prev;
        ++next;
        return query_max ? (prev->intersect(*next) <= prev->intersect(*it))
                        : (next->intersect(*prev) <= next->intersect(*it));
    }

    hulliter update_left_border(hulliter it) {
        if ((query_max && !has_prev(it)) || (!query_max && !has_next(it))) return it;
        hulliter it2 = it;
        double value = it->intersect(query_max ? *--it2 : *++it2);
        line l(*it);
        l.xlo = value;
        hull.erase(it++);
        return hull.insert(it, l);
    }

    public:
    ConvexHullTrick(bool query_max = false) : query_max(query_max) {}

    void add(long long m, long long b) {
        line l(m, b, 0, false, query_max);
        hulliter it = hull.lower_bound(l);
        if (it != hull.end() && it->m == l.m) {
            if ((query_max && it->b < b) || (!query_max && b < it->b)) hull.erase(it++);
            else return;
        }

        it = hull.insert(it, l);
        if (irrelevant(it)) {
            hull.erase(it);
            return;
        }

        while (has_prev(it) && irrelevant(--it)) hull.erase(it++);
        while (has_next(it) && irrelevant(++it)) hull.erase(it--);

        it = update_left_border(it);
        if (has_prev(it)) update_left_border(--it);
        if (has_next(++it)) update_left_border(++it);
    }

    long long query(long long x) const {
        line q(0, 0, x, true, query_max);
        hulliter it = hull.lower_bound(q);
        if (query_max) --it;
        return it->m*x + it->b;
    }
} slope;

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] + w[i];

    //dp(i) = max(dp(j) + f(i - 1) - f(j) + hi^2 + hj^2 - 2hihj | j < i)
    //dp(i) = max(-2hjhi + hj^2 + dp(j) - f(j) + f(i - 1) + hi^2 | j < i)
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    slope.add(-2 * h[1], 1LL * h[1] * h[1] + dp[1] - f[1]);
    for (int i = 2; i <= n; i++) {
        dp[i] = slope.query(h[i]) + f[i - 1] + 1LL * h[i] * h[i];
        slope.add(-2 * h[i], 1LL * h[i] * h[i] + dp[i] - f[i]);
    }

    printf("%lld", dp[n]);
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:99:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
                                  ~~~~~^~~~~~~~~~~~~
building.cpp:100:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
                                  ~~~~~^~~~~~~~~~~~~

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