oj.uz

Submission #161901

# Submission time Handle Problem Language Result Execution time Memory
161901 2019-11-05T08:57:11 Z amoo_safar Building Bridges (CEOI17_building) C++14
100 / 100
 167 ms 15996 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const ll Mod = 998244353;
const ll Inf = LONG_LONG_MAX;
const ll Log = 20;
const ll N = 1ll << Log;
const int Maxn = 1e5 + 10;
const int Maxk = 101;
const int Base = 101;


typedef pair < ll , ll > Line;
struct CHT{
    set < pair < Line , ll > > S;
    set < pair < ll , Line > > I;
    ll INF = 4e18;
    inline void Add(Line X)
    {
    	X.F *= -1;
    	X.S *= -1;
        ll t = -INF;
        auto it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.begin())
                {t = -INF; break;}
            it --; ll r = Intersection(it->first, X);
            if (r <= it->second)
                I.erase({it->second, it->first}), it = S.erase(it);
            else
                {t = r; break;}
        }
        it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.end())
                break;
            ll r = Intersection(X, it->first);
            Line Y = it->first;
            I.erase({it->second, it->first});
            it = S.erase(it);
            if (r <= t)
            {
                r = -INF;
                if (it != S.begin())
                    it --, r = Intersection(it->first, Y);
                S.insert({Y, r}); I.insert({r, Y}); return ;
            }
            if (it != S.end() && it->second <= r)
                continue;
            S.insert({Y, r}); I.insert({r, Y}); break;
        }
        S.insert({X, t}); I.insert({t, X});
    }
    inline ll GetMin(ll X)
    {
        auto it = I.upper_bound({X, {INF, INF}}); it --;
        return -(X * it->second.first + it->second.second);
    }
    inline ll Intersection(Line X, Line Y)
    {
        if (X.first == Y.first && X.second <= Y.second)
            return (-INF);
        if (X.first == Y.first)
            return (INF);
        return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0);
    }
};
CHT cht;

ll h[Maxn], w[Maxn], dp[Maxn], ps[Maxn];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	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++) ps[i] = ps[i - 1] + w[i];
	
	dp[1] = 0;
	cht.Add({-2LL * h[1], h[1] * h[1] + dp[1] - ps[1]});
	for(int i = 2; i <= n; i++){
		dp[i] = cht.GetMin(h[i]) + h[i] * h[i] + ps[i - 1];
		cht.Add({-2LL * h[i], h[i] * h[i] + dp[i] - ps[i]});	
	}
	cout << dp[n];
	return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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 380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3704 KB Output is correct
2 Correct 153 ms 3648 KB Output is correct
3 Correct 158 ms 3672 KB Output is correct
4 Correct 145 ms 3540 KB Output is correct
5 Correct 164 ms 5880 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 380 KB Output is correct
6 Correct 153 ms 3704 KB Output is correct
7 Correct 153 ms 3648 KB Output is correct
8 Correct 158 ms 3672 KB Output is correct
9 Correct 145 ms 3540 KB Output is correct
10 Correct 164 ms 5880 KB Output is correct
11 Correct 137 ms 3496 KB Output is correct
12 Correct 156 ms 3588 KB Output is correct
13 Correct 82 ms 3460 KB Output is correct
14 Correct 150 ms 3704 KB Output is correct
15 Correct 163 ms 15996 KB Output is correct
16 Correct 167 ms 6008 KB Output is correct
17 Correct 39 ms 3448 KB Output is correct
18 Correct 39 ms 3448 KB Output is correct