Submission #1034842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034842		MarwenElarbi	Building Bridges (CEOI17_building)	C++17	100 / 100	680 ms	10576 KiB

building

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e6+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll INF = 1e18;
struct lichao
{
    int N;
    lichao(int n)
    {
        N = n;
    }
    map<int , pair<ll,ll>> tree;
    ll f(pair<ll ,ll>line , ll x)
    {
        return line.first * x + line.second;
    }
    pair<ll ,ll> get(ll node)
    {
        return (tree.find(node) == tree.end() ? make_pair(0ll , INF) : tree[node]);
    }
    void add(ll node , int s, int e, pair<ll ,ll> new_line)
    {
        int m = (s + e)>>1;
        bool lef = f(new_line , s) < f(get(node) , s);
        bool mid = f(new_line , m) < f(get(node) , m);
        if(mid)
        {
            if(tree.find(node) != tree.end())
                swap(new_line ,tree[node]);
            else
            {
                tree[node] = new_line;
                new_line = {0 , INF};
            }
        }
        if(s + 1 == e)
            return ;
        if(mid != lef)
        {
            add(2*node , s , m , new_line);
        }
        else
            add(2*node +1 , m , e , new_line);
    }
    ll query(ll node , int s , int e , int x)
    {
        int m = (s + e)>>1;
        if(s + 1 == e){
            return f(get(node) , x);
        }
        if(x < m){
            return min(f(get(node) , x) , query(2*node , s , m , x));
        }
        else{

            return min(f(get(node) , x) , query(2*node + 1 , m , e , x));
        }
    }
    void add(pair<ll, ll> new_line)
    {
        add(1 , 0 , N , new_line);
    }
    ll query(int x)
    {
        return query(1 , 0 , N , x);
    }
};
int main()
{
    optimise;
    int n;
    cin>>n;
    ll h[n+1],w[n+1];
    for (int i = 1; i < n+1; ++i)
    {
        cin>>h[i];
    }
    for (int i = 1; i < n+1; ++i)
    {
        cin>>w[i];
    }
    long long pre[n+1];
    pre[0]=0;
    for (int i = 1; i < n+1; ++i)
    {
        pre[i]=w[i]+pre[i-1];
    }
    long long dp[n+1];
    lichao li(1e6);
    //cout <<li.query(5)<<endl;
    dp[0]=0;
    for (int i = 1; i < n+1; ++i)
    {
        dp[i]=( i!=1 ? li.query(h[i]) : 0)+h[i]*h[i]+pre[i-1];
        li.add({-2*h[i],dp[i]+(i!=1 ? h[i]*h[i] : 0)-pre[i]});
    }
    cout <<dp[n]<<endl;
}

        

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