oj.uz

Submission #161889

# Submission time Handle Problem Language Result Execution time Memory
161889 2019-11-05T07:48:16 Z shayan_p Building Bridges (CEOI17_building) C++14
100 / 100
 85 ms 9080 KB 
// 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2012 KB Output is correct
2 Correct 61 ms 3036 KB Output is correct
3 Correct 60 ms 3064 KB Output is correct
4 Correct 55 ms 2856 KB Output is correct
5 Correct 50 ms 4088 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 58 ms 2012 KB Output is correct
7 Correct 61 ms 3036 KB Output is correct
8 Correct 60 ms 3064 KB Output is correct
9 Correct 55 ms 2856 KB Output is correct
10 Correct 50 ms 4088 KB Output is correct
11 Correct 61 ms 3164 KB Output is correct
12 Correct 62 ms 3036 KB Output is correct
13 Correct 45 ms 3064 KB Output is correct
14 Correct 58 ms 3164 KB Output is correct
15 Correct 85 ms 9080 KB Output is correct
16 Correct 49 ms 4088 KB Output is correct
17 Correct 32 ms 2992 KB Output is correct
18 Correct 32 ms 2936 KB Output is correct