oj.uz

Submission #988387

# Submission time Handle Problem Language Result Execution time Memory
988387 2024-05-24T15:06:10 Z VMaksimoski008 Building Bridges (CEOI17_building) C++17
100 / 100
 117 ms 129192 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; }
};
 
struct LiChao {
    int n;
    vector<Line> tree;
 
    LiChao(int _n) {
        n = _n + 5;
        tree.resize(4*n, {(ll)-1e12, (ll)-1e18});
    }
 
    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 tot = 0;
	cin >> n;
    vector<ll> dp(n+1), h(n+1), w(n+1);
    LiChao cht(maxn);
 
	for(int i=1; i<=n; i++) cin >> h[i];
	for(int i=1; i<=n; i++) cin >> w[i], tot += w[i];
 
	dp[1] = -w[1];
	for(int i=2; i<=n; i++) {
		cht.insert({ 2 * h[i-1], -dp[i-1] - h[i-1] * h[i-1] });
		dp[i] = -cht.query(h[i]) - w[i] + h[i] * h[i];
	}
 
	cout << tot + dp[n] << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 125560 KB Output is correct
2 Correct 45 ms 125792 KB Output is correct
3 Correct 45 ms 125524 KB Output is correct
4 Correct 44 ms 125520 KB Output is correct
5 Correct 46 ms 125520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 127824 KB Output is correct
2 Correct 101 ms 129016 KB Output is correct
3 Correct 106 ms 129104 KB Output is correct
4 Correct 97 ms 128848 KB Output is correct
5 Correct 96 ms 128852 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 125560 KB Output is correct
2 Correct 45 ms 125792 KB Output is correct
3 Correct 45 ms 125524 KB Output is correct
4 Correct 44 ms 125520 KB Output is correct
5 Correct 46 ms 125520 KB Output is correct
6 Correct 103 ms 127824 KB Output is correct
7 Correct 101 ms 129016 KB Output is correct
8 Correct 106 ms 129104 KB Output is correct
9 Correct 97 ms 128848 KB Output is correct
10 Correct 96 ms 128852 KB Output is correct
11 Correct 117 ms 129032 KB Output is correct
12 Correct 109 ms 129192 KB Output is correct
13 Correct 109 ms 129104 KB Output is correct
14 Correct 111 ms 129108 KB Output is correct
15 Correct 93 ms 128852 KB Output is correct
16 Correct 102 ms 129160 KB Output is correct
17 Correct 90 ms 129104 KB Output is correct
18 Correct 92 ms 128900 KB Output is correct