Submission #1105057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105057		thanhnhanqn77	Building Bridges (CEOI17_building)	C++14	0 / 100	32 ms	5160 KiB

building

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bits/stdc++.h>
#define fu(i, a, b) for(int i = (a); i <= (b); i++)
#define fd(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define bit(mask, x) (mask & (1LL << x))
#define pi pair<int, int>
#define pl pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define nl cout << '\n';
#define pb push_back

using namespace std;
//#define double long double
const int N = (int)1e5 + 5;
int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[8] = {1, -1, 0, 0, -1, 1, -1, 1};
const ll INF = (ll)1e9 + 5;
const ll MOD = (ll)998244353;
const int LOG = 30;
const ll cow = 37;
const double eps = 0.0001;
const int M =(int)2e6 + 5;
template<class T1>
    void print(T1 a) {cout << a << ' ';}

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T1, class T2>
    void mul(T1 &a, T2 b) {a *= b; a%=MOD; return a;}

template<typename T, typename V>
void print(pair<T, V> &p) {print(p.fi); print(p.se);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < (int)v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v[i].size(); j++)
            print(v[i][j]);
        nl;
    }
}
template<typename T>
int sz(T x) {return (int)x.size();}

struct line
{
    ll a, b, c;
    line(ll _a = 0, ll _b = 0)
    {
        a = _a;
        b = _b;
    }
    ll get_val(ll x)
    {
        return a * x + b;
    }
};


vector<line> st;
int n;
ll h[N], w[N];
ll pref[N], dp[N];


bool so_sanh(line l1, line l2, line l3)
{
    ll p1 = (l1.a - l3.a) * (l2.b - l1.b);
    ll p2 = (l1.a - l2.a) * (l3.b - l1.b);
    return p1 > p2;
}
bool so_sanh2(line l1, line l2, line l3)
{
    ll p1 = (l1.a - l3.a) * (l2.b - l1.b);
    ll p2 = (l1.a - l2.a) * (l3.b - l1.b);
    return p1 > p2;
}


void addline(line a, int type)
{
    while(st.size() >= 2)
    {
        if((type == 1 && so_sanh(st[(int)st.size() - 2], st.back(), a)) || (type == 2 && so_sanh2(st[(int)st.size() - 2], st.back(), a))) st.pop_back();
        else break;
    }
    st.push_back(a);
}


ll querry_max(ll a)
{
    int l = 1, r = (int)st.size() - 1;
    int res = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(st[mid - 1].get_val(a) <= st[mid].get_val(a)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    ll val = 0;
    if((int)st.size() >= 1) val = st[0].get_val(a);
    return max(val, st[res].get_val(a));
}

ll querry_min(ll a)
{
    int l = 0, r = (int)st.size() - 1;
    int res = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(st[mid].get_val(a) <= st[mid + 1].get_val(a)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return st[res].get_val(a);
}





int main()
{//    freopen("tbrackets.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    t = 1;
    while(t--)
    {
        cin >> n;
        fu(i, 1, n) cin >> h[i];
        fu(i, 1, n) cin >> w[i];
        fu(i, 1, n) pref[i] = pref[i - 1] + w[i];
        addline(line(h[1], h[1] * h[1] - pref[1]), 1);
        dp[1] = 0;
        fu(i, 2, n)
        {
            ll val = querry_min(-2 * h[i]);
            dp[i] = val +  h[i] * h[i] + pref[i - 1];
            addline(line{h[i], dp[i] + h[i] * h[i] - pref[i]}, 1);
        }
        cout << dp[n];
    }
}

//7
//)()[](}

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