Submission #202251

#TimeUsernameProblemLanguageResultExecution timeMemory
202251thiago4532Building Bridges (CEOI17_building)C++17
100 / 100
182 ms12152 KiB
    #include <bits/stdc++.h>
    #define int int64_t
    using namespace std;
    const int maxn = 1e5 + 10;
    int h[maxn], pref[maxn], w[maxn];
    int n, dp[maxn];
     
    struct frac {
        int a, b;
     
        bool operator<(frac const& c) const {
            return a*c.b < c.a*b;
        }
    };
     
    bool flag = 0;
    struct line {
    	int a, b;
    	frac x;
     
    	bool operator<(line const& l) const {
    		if(flag == 0) return a > l.a;
    		else return x < l.x;
    	}
    };
     
    typedef set<line>::iterator sit;
     
    set<line> lines;
     
    bool hasPrev(sit it)
    {
    	return (it != lines.begin());
    }
     
    bool hasNext(sit it)
    {
    	return (next(it) != lines.end() && ++it != lines.end());
    }
     
    template<typename Arg>
    bool bad(Arg&& l1, Arg&& l2, Arg&& l3) {
    	return (l2.a - l1.a)*(l3.b - l1.b) >= (l3.a -  l1.a)*(l2.b - l1.b);
    }
     
    frac intersect(line const& l1, line const& l2) {
    	return {l2.b-l1.b, l1.a-l2.a};
    }
     
    void get_x(sit it) {
    	if (hasPrev(it))
    	{
    		line l = *it;
     
    		l.x = intersect(*prev(it), *it);
     
    		lines.erase(it); lines.insert(l);
    	}
    }
     
    void add(line const& l) {
    	auto it = lines.lower_bound(l);
    	if(it != lines.end() && it->a == l.a){
    		if(it->b <= l.b) return;
    		lines.erase(it);
    	}
     
    	lines.insert(l);
    	it = lines.find(l);
     
    	if (hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it))) {
    		lines.erase(it);
    		return;
    	}
     
    	while(hasNext(it) && hasNext(next(it)) && bad(*it, *next(it), *next(next(it)))) 
    		lines.erase(next(it));
     
    	while(hasPrev(it) && hasPrev(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
    		lines.erase(prev(it));
     
        if (hasNext(it)) get_x(next(it));
    	get_x(it);
    }
     
    inline int f(line const& l, int x) {
    	return l.a*x + l.b;
    }
     
    int query(int x) {
    	flag = true;
    	auto it = lines.upper_bound({0, 0, {x, 1}});
    	flag = false;
    	it--;
    	return f(*it, x);
    }
     
     
    int32_t main() {
    	cin >> n;
    	for(int i=1;i<=n;i++)
    		cin >> h[i];
     
    	for(int i=1;i<=n;i++)
    		cin >> w[i], pref[i] = pref[i-1] + w[i];
     
    	dp[1] = 0;
    	add({-2*h[1], h[1]*h[1] + dp[1] - pref[1]});
     
    	for(int i=2;i<=n;i++) {
    		// dp[i] = 0x3f3f3f3f3f3f3f3f;
     
    		// for(int j=1;j<i;j++) {
    		// 	dp[i] = min(dp[i], dp[j] - pref[j] + h[j]*h[j] - 2*h[j] * h[i]);
    		// }
     
    		dp[i] = query(h[i]);
     
    		dp[i] += h[i]*h[i] + pref[i-1];
    		add({-2*h[i], h[i]*h[i] + dp[i] - pref[i]});
    	}
    	cout << dp[n] << "\n";
    	return 0;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...