oj.uz

Submission #938573

# Submission time Handle Problem Language Result Execution time Memory
938573 2024-03-05T10:22:39 Z VMaksimoski008 Building Bridges (CEOI17_building) C++14
0 / 100
 83 ms 65468 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 = 1e6 + 5;
const double eps = 1e-9;

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

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<int> h(n), w(n);
    for(int &x : h) cin >> x;
    for(int &x : w) cin >> x, ans += x;

    LiChao cht(maxn);

    vector<ll> dp(n);
    dp[0] = -w[0];
    cht.insert({ 2 * h[0], -dp[0] - h[0] * h[0] });

    for(int i=1; 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 << ans + dp[n-1] << '\n';
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62900 KB Output is correct
2 Correct 9 ms 63068 KB Output is correct
3 Correct 10 ms 63068 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Incorrect 10 ms 62908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 65468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62900 KB Output is correct
2 Correct 9 ms 63068 KB Output is correct
3 Correct 10 ms 63068 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Incorrect 10 ms 62908 KB Output isn't correct
6 Halted 0 ms 0 KB -