oj.uz

답안 #840499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840499 2023-08-31T12:43:13 Z taitruong270 Building Bridges (CEOI17_building) C++17
100 / 100
 59 ms 11604 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;

struct LiChao_tree       //offline + get min
{
    struct line 
    {
        ll a, b;
        ll get(ll x) {return a*x+b;}
    };
 
    ll n;
    vector<line> tree;
    vector<ll> compress;
 
    LiChao_tree(vector<ll> _compress_x)
    {
        n=_compress_x.size()+5;
        compress=_compress_x;
        sort(compress.begin(), compress.end());
        compress.resize(unique(compress.begin(), compress.end())-compress.begin());
        tree.resize(4*n+5, {0, LLONG_MAX});       //LLONG_MIN
    }

    ll getid(ll val) {return lower_bound(compress.begin(), compress.end(), val)-compress.begin();}
 
    void insert(ll id, ll l, ll r, line newL)
    {
        if (l==r)
        {
            if (newL.get(compress[l])<tree[id].get(compress[l])) tree[id]=newL;    //thay dau >
            return;
        }
        ll m=(l+r)/2;
        bool lef=newL.get(compress[l])<tree[id].get(compress[l]);    //thay dau >
        bool mid=newL.get(compress[m])<tree[id].get(compress[m]);    //thay dau >
        if (mid==true) swap(newL, tree[id]);
        if (lef!=mid) insert(id*2, l, m, newL);
        else insert(id*2+1, m+1, r, newL);
    }

    void insert(ll a, ll b)
    {
        line newL={a, b};
        insert(1, 0, n-1, newL);
    }
 
    ll query(ll id, ll l, ll r, ll x)
    {
        if (l==r) return tree[id].get(compress[x]);
        ll m=(l+r)/2;
        if (x<=m) return min(tree[id].get(compress[x]), query(id*2, l, m, x));   //max()
        return min(tree[id].get(compress[x]), query(id*2+1, m+1, r, x));   //max()
    }
 
    ll query(ll x)
    {
        ll pos=getid(x);
        return query(1, 0, n-1, pos);
    }
};
ll n, tot, h[100005], w[100005], dp[100005];

void solve()
{
    cin>>n;
    for (ll i=1; i<=n; i++) cin>>h[i];
    for (ll i=1; i<=n; i++) cin>>w[i];
    vector<ll> v;
    for (ll i=1; i<=n; i++) v.push_back(h[i]), tot+=w[i];
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end())-v.begin());
    LiChao_tree seg(v);
    dp[1]=-w[1];
    for (ll i=2; i<=n; i++)
    {
        seg.insert(-2*h[i-1], dp[i-1]+h[i-1]*h[i-1]);
        dp[i]=seg.query(h[i])-w[i]+h[i]*h[i];
    }
    cout<<tot+dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 412 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 3956 KB Output is correct
2 Correct 49 ms 5064 KB Output is correct
3 Correct 43 ms 5064 KB Output is correct
4 Correct 36 ms 4516 KB Output is correct
5 Correct 36 ms 11472 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 43 ms 3956 KB Output is correct
7 Correct 49 ms 5064 KB Output is correct
8 Correct 43 ms 5064 KB Output is correct
9 Correct 36 ms 4516 KB Output is correct
10 Correct 36 ms 11472 KB Output is correct
11 Correct 59 ms 9540 KB Output is correct
12 Correct 55 ms 9388 KB Output is correct
13 Correct 34 ms 4680 KB Output is correct
14 Correct 55 ms 9496 KB Output is correct
15 Correct 37 ms 11472 KB Output is correct
16 Correct 40 ms 11604 KB Output is correct
17 Correct 16 ms 4560 KB Output is correct
18 Correct 14 ms 4560 KB Output is correct