Submission #996380

#	Time	Username	Problem	Language	Result	Execution time	Memory
996380		dimonce	Building Bridges (CEOI17_building)	C++17	30 / 100	41 ms	4176 KiB

building

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct seg{
    mutable int l,r,k,b,type;
    bool operator<(const seg &a) const {
        if (type==1 or a.type==1){
            return l<a.l;
        }
        if (type==2 or a.type==2){
            return k>a.k;
        }
        return l<a.l;
    }
};

set<seg> st;

int minimize(int l){
    auto it = *(--st.upper_bound({l, 1000000, 0, 0, 1}));
    return it.k*l+it.b;
}

double intersection (int k1, int b1, int k2, int b2){
    return (b1-b2)/(k2-k1);
}

void insert(int k, int b){
    auto it1 = st.lower_bound({0, 0, k, 0, 2});
    if (it1!=st.end() and it1->k==k){
        if (b>=it1->b) return;
        it1=st.erase(it1);
    }
    if (it1==st.begin()) it1=st.end();
    else{
        --it1;
        while (intersection(it1->k, it1->b, k, b) < it1->r){
            double inter=intersection(it1->k, it1->b, k, b);
            if (inter < it1->l) it1=--st.erase(it1);
            else{
                it1->r=floor(inter);
                break;
            }
        }
    }
    
    auto it2 = st.upper_bound({0, 0, k, 0, 2});
    while (it2!=st.end() and intersection(it2->k, it2->b, k, b) > it2->l){
        double inter=intersection(it2->k, it2->b, k, b);
        if (inter > it2->r) it2=st.erase(it2);
        else{
            it2->l=ceil(inter+1);
            break;
        }
    }
    
    if (it2==st.end() or it1==st.end() or it1->r+1<it2->l){
        st.insert({it1==st.end() ? (int)0 : it1->r+1, it2==st.end() ? (int)1e6 : it2->l-1, k, b, 0});
    }
    
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int arr[n], w[n], sum=0;
    for (int i=0; i<n; ++i){
        cin>>arr[i];
    }
    for (int i=0; i<n; ++i){
        cin>>w[i];
        sum+=w[i];
    }
    int dp[n];
    dp[0]=-w[0];
    st.insert({0, 1000000, -2*arr[0], arr[0]*arr[0]+dp[0], 0});
    int x;
    for (int i=1; i<n; ++i){
        x=minimize(arr[i]);
        dp[i]=x+arr[i]*arr[i]-w[i];
        insert(-2*arr[i], dp[i]+arr[i]*arr[i]);
        // cout<<dp[i]<<' ';
    }
    cout<<dp[n-1]+sum<<'\n';
    return 0;
}

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