Submission #938585

#	Time	Username	Problem	Language	Result	Execution time	Memory
938585		VMaksimoski008	Building Bridges (CEOI17_building)	C++14	0 / 100	81 ms	128072 KiB

building

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40