oj.uz

Submission #484469

# Submission time Handle Problem Language Result Execution time Memory
484469 2021-11-03T15:21:00 Z hoanghq2004 Building Bridges (CEOI17_building) C++14
100 / 100
 61 ms 9264 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1564 KB Output is correct
2 Correct 42 ms 1564 KB Output is correct
3 Correct 42 ms 1520 KB Output is correct
4 Correct 40 ms 1416 KB Output is correct
5 Correct 43 ms 3024 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 43 ms 1564 KB Output is correct
7 Correct 42 ms 1564 KB Output is correct
8 Correct 42 ms 1520 KB Output is correct
9 Correct 40 ms 1416 KB Output is correct
10 Correct 43 ms 3024 KB Output is correct
11 Correct 40 ms 1516 KB Output is correct
12 Correct 45 ms 1484 KB Output is correct
13 Correct 36 ms 1464 KB Output is correct
14 Correct 44 ms 1556 KB Output is correct
15 Correct 61 ms 9264 KB Output is correct
16 Correct 43 ms 3004 KB Output is correct
17 Correct 19 ms 1424 KB Output is correct
18 Correct 20 ms 2564 KB Output is correct