oj.uz

Submission #938579

# Submission time Handle Problem Language Result Execution time Memory
938579 2024-03-05T10:28:41 Z VMaksimoski008 Building Bridges (CEOI17_building) C++14
0 / 100
 77 ms 129052 KB 
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e6 + 5;
const double eps = 1e-9;

struct Line {
    ll m, b;
    ll operator()(ll x) { return m * x + b; }
};

//for maximum
struct LiChao {
    int n;
    vector<Line> tree;

    LiChao(int _n) {
        n = _n + 5;
        tree.resize(4*n);
    }

    void insert(int u, int tl, int tr, Line seg) {
        if(tl + 1 == tr) {
            if(seg(tl) > tree[u](tl)) tree[u] = seg;
            return ;
        }

        int tm = (tl + tr) / 2;
        if(tree[u].m > seg.m) swap(tree[u], seg);
        if(tree[u](tm) < seg(tm)) {
            swap(tree[u], seg);
            insert(2*u+1, tl, tm, seg);
        } else insert(2*u+2, tm, tr, seg);
    }

    ll query(int u, int tl, int tr, int p) {
        if(tl + 1 == tr) return tree[u](p);
        int tm = (tl + tr) / 2;
        if(p < tm) return max(tree[u](p), query(2*u+1, tl, tm, p));
        return max(tree[u](p), query(2*u+2, tm, tr, p));
    }

    void insert(Line line) { insert(0, 0, n, line); }
    ll query(ll v) { return query(0, 0, n, v); }
};

int main() {
    int n;
    ll ans = 0;
    cin >> n;

    vector<ll> h(n+1), w(n+1);
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1; i<=n; i++) cin >> w[i], ans += w[i];

    vector<ll> dp(n+1);
    LiChao cht(maxn);
    dp[1] = -w[1];

    cht.insert({ 2 * h[1], -dp[1] - h[1] * h[1] });

    for(int i=2; i<=n; i++) {
        dp[i] = -cht.query(h[i]) + h[i] * h[i] - w[i];
        cht.insert({ 2 * h[i], -dp[i] - h[i] * h[i] });
    }

    cout << dp[n] + ans << '\n';
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 125524 KB Output is correct
2 Correct 18 ms 125532 KB Output is correct
3 Correct 19 ms 125532 KB Output is correct
4 Correct 19 ms 125528 KB Output is correct
5 Incorrect 19 ms 125532 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 127828 KB Output is correct
2 Correct 75 ms 129048 KB Output is correct
3 Correct 74 ms 129052 KB Output is correct
4 Correct 73 ms 128836 KB Output is correct
5 Incorrect 68 ms 128848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 125524 KB Output is correct
2 Correct 18 ms 125532 KB Output is correct
3 Correct 19 ms 125532 KB Output is correct
4 Correct 19 ms 125528 KB Output is correct
5 Incorrect 19 ms 125532 KB Output isn't correct
6 Halted 0 ms 0 KB -