oj.uz

Submission #200267

# Submission time Handle Problem Language Result Execution time Memory
200267 2020-02-05T21:14:06 Z alishahali1382 Building Bridges (CEOI17_building) C++14
100 / 100
 176 ms 16120 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG=20;

struct CHT{
    typedef pair < ll , ll > Line;
	set < pair < Line , ll > > S;
    set < pair < ll , Line > > I;
    ll INF = 4e18;
    inline void Add(Line X)
    {
        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 GetMax(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);
    }
};

ll n, m, k, u, v, x, y, t, a, b, ans;
ll A[MAXN], B[MAXN];
ll dp[MAXN];
CHT cht;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>A[i];
	for (int i=1; i<=n; i++) cin>>B[i], ans+=B[i];
	dp[1]=-B[1];
	cht.Add({-A[1], -A[1]*A[1]-dp[1]});
	for (int i=2; i<=n; i++){
		dp[i]=-cht.GetMax(-2*A[i]) + A[i]*A[i] - B[i];
		cht.Add({-A[i], -A[i]*A[i]-dp[i]});
	}
	ans+=dp[n];
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3936 KB Output is correct
2 Correct 142 ms 3832 KB Output is correct
3 Correct 136 ms 3832 KB Output is correct
4 Correct 131 ms 3708 KB Output is correct
5 Correct 113 ms 6052 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 536 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 140 ms 3936 KB Output is correct
7 Correct 142 ms 3832 KB Output is correct
8 Correct 136 ms 3832 KB Output is correct
9 Correct 131 ms 3708 KB Output is correct
10 Correct 113 ms 6052 KB Output is correct
11 Correct 129 ms 3980 KB Output is correct
12 Correct 145 ms 3832 KB Output is correct
13 Correct 80 ms 3836 KB Output is correct
14 Correct 136 ms 4092 KB Output is correct
15 Correct 176 ms 16120 KB Output is correct
16 Correct 114 ms 6008 KB Output is correct
17 Correct 45 ms 3704 KB Output is correct
18 Correct 43 ms 3704 KB Output is correct