oj.uz

Submission #1112363

# Submission time Handle Problem Language Result Execution time Memory
1112363 2024-11-14T06:38:07 Z Aviansh Building Bridges (CEOI17_building) C++17
100 / 100
 122 ms 51528 KB 
#include <bits/stdc++.h>

using namespace std;

long long inf = 2e18;

struct line{
    long long m;
    long long c;
    double val(double x){
        return m*x+c;
    }
    int left=-1;
    int right=-1;
};

struct liChaoTree{
    line *st;
    line def;
    int cr = 0;
    liChaoTree(int nodes){
        def.m=0;
        def.c=LLONG_MAX;
        st=new line[nodes];
        fill(st,st+nodes,def);
    }
    void addLine(line lin, long long l=0, long long r=1e9+5, int ind=0){
        long long mid = (l+r)/2;
        if(st[ind].val(l)<=lin.val(l)&&st[ind].val(r)<=lin.val(r)){
            return;
        }
        lin.left=st[ind].left;
        lin.right=st[ind].right;
        if(st[ind].val(mid)>lin.val(mid)){
            swap(lin,st[ind]);
        }
        if(l==r)
            return;
        else if(st[ind].val(l)>lin.val(l)){
            if(lin.left==-1){
                cr++;
                st[ind].left=cr;
            }
            addLine(lin,l,mid,st[ind].left);
        }
        else{
            if(lin.right==-1){
                cr++;
                st[ind].right=cr;
            }
            addLine(lin,mid+1,r,st[ind].right);
        }
    }
    double query(long long x, long long l=0, long long r=1e9+5, int ind=0){
        if(l==r&&r==x){
            return st[ind].val(x);
        }
        if(x<l||x>r){
            return def.val(x);
        }
        long long mid = (l+r)/2;
        double ans1 = 2e18;
        if(st[ind].left!=-1){
            ans1=query(x,l,mid,st[ind].left);
        }

        double ans2 = 2e18;
        if(st[ind].right!=-1){
            ans2=query(x,mid+1,r,st[ind].right);
        }
        return min({st[ind].val(x),ans1,ans2});
    }
};


signed main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    long long n;
    cin >> n;
    long long arr[n];
    for(long long &i : arr){
        cin >> i;
    }
    long long w[n];
    for(long long &i : w){
        cin >> i;
    }
    long long dp[n];
    dp[0]=0;
    dp[1]=arr[0]*arr[0]+arr[1]*arr[1]-2*arr[0]*arr[1];
    long long pref[n];
    pref[0]=w[0];
    for(int i = 1;i<n;i++){
        pref[i]=pref[i-1]+w[i];
    }
    liChaoTree lct(2e6+50);
    line l1,l2;
    l1.m=-2*arr[0];
    l2.m=-2*arr[1];
    l1.c=dp[0]-pref[0]+arr[0]*arr[0];
    l2.c=dp[1]-pref[1]+arr[1]*arr[1];
    //cout << "adding: \n";
    lct.addLine(l1);
    lct.addLine(l2);
    for(long long i = 2;i<n;i++){
        dp[i]=inf;
        //cout << dp[i] << " " << lct.query(arr[i]) << "\n";
        dp[i]=lct.query(arr[i]);
        dp[i]+=pref[i-1]+arr[i]*arr[i];
        line t;
        t.m=-2*arr[i];
        t.c=dp[i]-pref[i]+arr[i]*arr[i];
        lct.addLine(t);
    }
    cout << dp[n-1];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47184 KB Output is correct
2 Correct 32 ms 47184 KB Output is correct
3 Correct 34 ms 47184 KB Output is correct
4 Correct 33 ms 47436 KB Output is correct
5 Correct 39 ms 47432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 51528 KB Output is correct
2 Correct 117 ms 51528 KB Output is correct
3 Correct 122 ms 51528 KB Output is correct
4 Correct 108 ms 51240 KB Output is correct
5 Correct 105 ms 51268 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47184 KB Output is correct
2 Correct 32 ms 47184 KB Output is correct
3 Correct 34 ms 47184 KB Output is correct
4 Correct 33 ms 47436 KB Output is correct
5 Correct 39 ms 47432 KB Output is correct
6 Correct 117 ms 51528 KB Output is correct
7 Correct 117 ms 51528 KB Output is correct
8 Correct 122 ms 51528 KB Output is correct
9 Correct 108 ms 51240 KB Output is correct
10 Correct 105 ms 51268 KB Output is correct
11 Correct 116 ms 51528 KB Output is correct
12 Correct 122 ms 51528 KB Output is correct
13 Correct 104 ms 51528 KB Output is correct
14 Correct 119 ms 51528 KB Output is correct
15 Correct 95 ms 51272 KB Output is correct
16 Correct 99 ms 51340 KB Output is correct
17 Correct 68 ms 51528 KB Output is correct
18 Correct 66 ms 51528 KB Output is correct