제출 #123816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123816		FutymyClone	Building Bridges (CEOI17_building)	C++14	0 / 100	40 ms	3704 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];

int state (int a, int b) {
    return a > b ? 1 : (a < b ? -1 : 0);
}

struct ConvexHullTrick {
    struct Line {
        long long a, b; // y = ax + b
        mutable function <const Line*()> succ;
        Line (long long a, long long b): a(a), b(b) {};
        bool operator < (const Line &rhs) const {
            if (rhs.b != inf) return a < rhs.a;
            const Line* s = succ();
            if (!s) return false;
            int x = rhs.a;
            return b - s -> b < (s -> a - a) * x;
        }
    };

    multiset <Line> s;
    bool bad (multiset <Line> ::iterator x) {
        auto z = next(x);
        if (x == s.begin()) {
            if (z == s.end()) return false;
            return x -> a == z -> a && x -> b <= z -> b;
        }

        auto y = prev(x);
        if (z == s.end()) return x -> a == y -> a && x -> b <= y -> b;

        int l1 = state(y -> b, x -> b), l2 = state(z -> a, x -> a), r1 = state(x -> b, z -> b), r2 = state(x -> a, y -> a);
        int lef = l1 * l2, rig = r1 * r2;
        if (lef == 0 && rig == 0) return true;
        if (lef != rig) return lef > rig;

        long double val1 = (long double)(y -> b - x -> b) / (x -> b - z -> b);
        long double val2 = (long double)(x -> a - y -> a) / (z -> a - x -> a);
        if (lef == 1 && rig == 1) return val1 >= val2;
        return val1 <= val2;
    }

    void add (long long a, long long b) {
        auto x = s.insert(Line(a, b));
        x -> succ = [=] {
            return next(x) == s.end() ? 0 : &*next(x);
        };

        if (bad(x)) {
            s.erase(x);
            return;
        }

        while (next(x) != s.end() && bad(next(x))) s.erase(next(x));
        while (x != s.begin() && bad(prev(x))) s.erase(prev(x));
    }

    long long query (long long x) {
        if (s.size() == 0) return 0;
        auto found = *s.lower_bound(Line(x, inf));
        return found.a * x + found.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
*/

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'int main()':
building.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:75: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:76: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