oj.uz

Submission #996387

# Submission time Handle Problem Language Result Execution time Memory
996387 2024-06-10T14:28:33 Z dimonce Building Bridges (CEOI17_building) C++14
100 / 100
 63 ms 11320 KB 
#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);
}

bool show=false;

void insert(int k, int b){
    if (show) cout<<1<<endl;
    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 (show) cout<<1<<endl;
    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){
                if (it1==st.begin()){
                    st.erase(it1);
                    it1=st.end();
                    break;
                }
                it1=--st.erase(it1);
            }
            else{
                it1->r=floor(inter);
                break;
            }
        }
    }
    
    if (show) cout<<1<<endl;
    
    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 (show) cout<<1<<endl;
    
    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});
    }
    
    if (show) cout<<1<<endl;
}

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){
        // if (i==11) show=true;
        x=minimize(arr[i]);
        dp[i]=x+arr[i]*arr[i]-w[i];
        insert(-2*arr[i], dp[i]+arr[i]*arr[i]);
        // if (i==11) return 0;
        // cout<<dp[i]<<' ';
    }
    cout<<dp[n-1]+sum<<'\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2652 KB Output is correct
2 Correct 34 ms 2840 KB Output is correct
3 Correct 33 ms 2652 KB Output is correct
4 Correct 34 ms 2652 KB Output is correct
5 Correct 43 ms 4108 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 33 ms 2652 KB Output is correct
7 Correct 34 ms 2840 KB Output is correct
8 Correct 33 ms 2652 KB Output is correct
9 Correct 34 ms 2652 KB Output is correct
10 Correct 43 ms 4108 KB Output is correct
11 Correct 34 ms 3924 KB Output is correct
12 Correct 39 ms 3872 KB Output is correct
13 Correct 26 ms 3672 KB Output is correct
14 Correct 42 ms 3932 KB Output is correct
15 Correct 63 ms 11320 KB Output is correct
16 Correct 44 ms 4948 KB Output is correct
17 Correct 13 ms 3676 KB Output is correct
18 Correct 17 ms 3676 KB Output is correct