oj.uz

Submission #484468

# Submission time Handle Problem Language Result Execution time Memory
484468 2021-11-03T15:15:08 Z hoanghq2004 Building Bridges (CEOI17_building) C++14
60 / 100
 62 ms 9768 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], s[Nmax];
long long f[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({2 * h[i], - 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 1 ms 316 KB Output is correct
3 Correct 1 ms 332 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 1324 KB Output is correct
2 Correct 43 ms 2204 KB Output is correct
3 Correct 43 ms 2124 KB Output is correct
4 Correct 46 ms 2048 KB Output is correct
5 Correct 52 ms 3516 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 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 1324 KB Output is correct
7 Correct 43 ms 2204 KB Output is correct
8 Correct 43 ms 2124 KB Output is correct
9 Correct 46 ms 2048 KB Output is correct
10 Correct 52 ms 3516 KB Output is correct
11 Correct 46 ms 2312 KB Output is correct
12 Correct 44 ms 2164 KB Output is correct
13 Correct 32 ms 2124 KB Output is correct
14 Correct 42 ms 2324 KB Output is correct
15 Correct 62 ms 9768 KB Output is correct
16 Correct 54 ms 3500 KB Output is correct
17 Incorrect 21 ms 2044 KB Output isn't correct
18 Halted 0 ms 0 KB -