제출 #161889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161889		shayan_p	Building Bridges (CEOI17_building)	C++14	100 / 100	85 ms	9080 KiB

building

// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;

int a[maxn], b[maxn];
ll lz, dp[maxn];

bool Q;
struct Line 
{
	mutable ll k, m, p;
	bool operator<(const Line& o) const 
	{
		return Q ? p < o.p : k < o.k;
	}
};
struct CHT : multiset<Line> 
{
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) 
    {
	// floored division
	return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) 
    {
	if (y == end())
	    {
		x->p = inf;
		return false;
	    }
	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(ll k, ll m) 
    {
	auto z = insert({k, m, 0}), y = z++, x = y;
	while (isect(y, z))
	    z = erase(z);
	if (x != begin() && isect(--x, y))
	    isect(x, y = erase(y));
	while ((y = x) != begin() && (--x)->p >= y->p)
	    isect(x, erase(y));
    }
    ll query(ll x) 
    {
	assert(!empty());
	Q = 1; 
	auto l = *lower_bound({0, 0, x});
	Q = 0;
	return l.k * x + l.m;
    }
};

CHT cht;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n; cin>>n;
    for(int i=0;i<n;i++){
	cin>>a[i];
    }
    for(int i=0;i<n;i++){
	cin>>b[i];
    }
    cht.add(2*a[0], -1ll*a[0]*a[0]);
    for(int i=1;i<n;i++){
	dp[i]= -cht.query(a[i]) + lz + 1ll*a[i]*a[i];
	lz+= b[i];
	cht.add(2*a[i], -1ll*a[i]*a[i] - dp[i] +lz);
    }
    return cout<<dp[n-1]<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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