oj.uz

Submission #938585

# Submission time Handle Problem Language Result Execution time Memory
938585 2024-03-05T10:35:19 Z VMaksimoski008 Building Bridges (CEOI17_building) C++14
0 / 100
 81 ms 128072 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);
    }
 
    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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 125520 KB Output is correct
2 Correct 19 ms 125528 KB Output is correct
3 Correct 19 ms 125648 KB Output is correct
4 Correct 20 ms 125472 KB Output is correct
5 Incorrect 19 ms 125528 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 127836 KB Output is correct
2 Correct 80 ms 128072 KB Output is correct
3 Correct 77 ms 128028 KB Output is correct
4 Correct 71 ms 128028 KB Output is correct
5 Incorrect 76 ms 127988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 125520 KB Output is correct
2 Correct 19 ms 125528 KB Output is correct
3 Correct 19 ms 125648 KB Output is correct
4 Correct 20 ms 125472 KB Output is correct
5 Incorrect 19 ms 125528 KB Output isn't correct
6 Halted 0 ms 0 KB -