Submission #959841

#	Time	Username	Problem	Language	Result	Execution time	Memory
959841		dosts	Building Bridges (CEOI17_building)	C++17	100 / 100	37 ms	10588 KiB

building

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+1,inf = 1e18;

struct Line {
	mutable int k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(int x) const { return p < x; }
};

struct CHT : multiset<Line, less<>> {
	int div(int a, int b) { // floored division
		return (a / b) - ((a ^ b) < 0 && a % b); 
    }
	bool intersect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(int k, int m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (intersect(y, z)) z = erase(z);
		if (x != begin() && intersect(--x, y)) intersect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) intersect(x, erase(y));
	}
	int query(int x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

void solve() {
    int n;
    cin >> n;
    vi h(n+1),w(n+1),W(n+1,0);
    for (int i=1;i<=n;i++) cin >> h[i];
    for (int i=1;i<=n;i++) cin >> w[i];
    for (int i=1;i<=n;i++) W[i] = W[i-1]+w[i];
    CHT cht;
    vi dp(n+1);
    cht.add(2*h[1],-h[1]*h[1]+W[1]);
    for (int i=2;i<=n;i++) {
        dp[i] = W[i-1]+h[i]*h[i]-cht.query(h[i]);
        cht.add(2*h[i],-h[i]*h[i]+W[i]-dp[i]);
    }
    cout << dp[n] << '\n';
}
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40