Submission #484469

#	Time	Username	Problem	Language	Result	Execution time	Memory
484469		hoanghq2004	Building Bridges (CEOI17_building)	C++14	100 / 100	61 ms	9264 KiB

building

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int Nmax = 1e5 + 10;

int n, h[Nmax];
long long s[Nmax];
int mode;

struct line {
    long long a, b;
    mutable long double x;
    int operator < (const line& other) const {
        return (!mode ? a < other.a : x < other.x);
    }
};

struct convex: multiset <line> {
    int del(iterator u, iterator v) {
        if (v == end()) {
            u -> x = 1e18;
            return 0;
        }
        if (u -> a == v -> a) u -> x = (u -> b > v -> b ? 1e18 : -1e18);
        else u -> x = (long double)(u -> b - v -> b) / (v -> a - u -> a);
        return (u -> x >= v -> x);
    }
    void add(line l) {
        auto w = insert(l);
        auto u = w, v = w; ++w;
        while (del(u, w)) w = erase(w);
        if (u != begin() && del((--u), v)) {
            v = erase(v);
            del(u, v);
        }
        while ((v = u) != begin() && del((--u), v)) {
            v = erase(v);
            del(u, v);
        }
    }
    long long get(long long x) {
        if (empty()) return 0;
        mode = 1;
        auto l = *lower_bound({0, 0, x});
        mode = 0;
        return l.a * x + l.b;
    }
} cht;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= n; ++i) s[i] += s[i - 1];
    cht.add({2 * h[1], s[1] - 1LL * h[1] * h[1]});
    long long now = 0;
    for (int i = 2; i <= n; ++i) {
        now = - cht.get(h[i]) + 1LL * h[i] * h[i] + s[i - 1];
        cht.add({h[i] * 2, - now + s[i] - 1LL * h[i] * h[i]});
    }
    cout << now;
}
// (- 2 * h[i] * h[j]) + (f[j] - s[j] + h[j] * h[j]) + (h[i] * h[i] + s[i - 1])

Compilation message (stderr)

building.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
building.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
building.cpp: In member function 'long long int convex::get(long long int)':
building.cpp:48:38: warning: narrowing conversion of 'x' from 'long long int' to 'long double' [-Wnarrowing]
   48 |         auto l = *lower_bound({0, 0, x});
      |                                      ^

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