oj.uz

Submission #1112158

# Submission time Handle Problem Language Result Execution time Memory
1112158 2024-11-13T17:30:49 Z Aviansh Building Bridges (CEOI17_building) C++17
100 / 100
 88 ms 37552 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;
    }
};

struct liChaoTree{
    line *st;
    line def;
    int n;
    liChaoTree(int siz){
        def.m=0;
        def.c=LLONG_MAX;
        int x = (int)ceil(log2(siz));
        st=new line[(1<<(x+1))];
        fill(st,st+(1<<(x+1)),def);
        n=siz;
    }
    void addLine(line lin, long long l=0, long long r=1000005, 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;
        }
        if(st[ind].val(mid)>lin.val(mid)){
            swap(lin,st[ind]);
            //cout << "set " << ind << " to " << st[ind].m << " " << st[ind].c << "\n";
        }
        if(l==r)
            return;
        else if(st[ind].val(l)>lin.val(l)){
            addLine(lin,l,mid,2*ind+1);
        }
        else{
            addLine(lin,mid+1,r,2*ind+2);
        }
        //cout << "added smth" << "\n";
    }
    double query(long long x, long long l=0, long long r=1000005, int ind=0){
        if(l==r&&r==x){
            //cout << "got " << st[ind].val(x) << " from " << st[ind].m << " " << st[ind].c << "\n";
            return st[ind].val(x);
        }
        if(x<l||x>r){
            return def.val(x);
        }
        long long mid = (l+r)/2;
        return min({st[ind].val(x),query(x,l,mid,ind*2+1),query(x,mid+1,r,ind*2+2)});
    }
};

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(1000005);
    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 5 ms 33104 KB Output is correct
2 Correct 4 ms 33292 KB Output is correct
3 Correct 5 ms 33104 KB Output is correct
4 Correct 6 ms 33104 KB Output is correct
5 Correct 6 ms 33192 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 36392 KB Output is correct
2 Correct 73 ms 36168 KB Output is correct
3 Correct 82 ms 36184 KB Output is correct
4 Correct 68 ms 36176 KB Output is correct
5 Correct 61 ms 36180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33104 KB Output is correct
2 Correct 4 ms 33292 KB Output is correct
3 Correct 5 ms 33104 KB Output is correct
4 Correct 6 ms 33104 KB Output is correct
5 Correct 6 ms 33192 KB Output is correct
6 Correct 71 ms 36392 KB Output is correct
7 Correct 73 ms 36168 KB Output is correct
8 Correct 82 ms 36184 KB Output is correct
9 Correct 68 ms 36176 KB Output is correct
10 Correct 61 ms 36180 KB Output is correct
11 Correct 81 ms 37424 KB Output is correct
12 Correct 78 ms 37192 KB Output is correct
13 Correct 72 ms 37448 KB Output is correct
14 Correct 88 ms 37552 KB Output is correct
15 Correct 61 ms 37192 KB Output is correct
16 Correct 63 ms 37208 KB Output is correct
17 Correct 50 ms 37464 KB Output is correct
18 Correct 47 ms 37448 KB Output is correct