oj.uz

Submission #988661

# Submission time Handle Problem Language Result Execution time Memory
988661 2024-05-25T12:04:06 Z Aviansh Building Bridges (CEOI17_building) C++17
30 / 100
 68 ms 68444 KB 
#include <bits/stdc++.h>

using namespace std;

struct line{
    double m,c;
    double eval(double x){
        return (m*x)+c;
    }
    double intersect(line l){
        return (l.c-c)/(m-l.m);
    }
};

template<class T> class liChaoTree{
    private:
        int n;
        line *st;
        line def = {0,INT_MAX};
    public:
        liChaoTree(int siz){
            int x = (int) pow(2,ceil(log2(siz)));
            n=siz-1;
            st=new line[2*x];
            realST(0,n,0);
        }
        void realST(int l, int r, int ind){
            st[ind]=def;
            if(l!=r){
                int mid = (l+r)/2;
                realST(l,mid,ind*2+1);
                realST(mid+1,r,ind*2+2);
            }
        }
        double realQuer(double x, int l, int r, int ind){
            int mid = (l+r)/2;
            if(r-l==1){
                return st[ind].eval(x);
            }
            else if(x<mid){
                return min(st[ind].eval(x),realQuer(x,l,mid,ind*2+1));
            }
            else{
                return min(st[ind].eval(x),realQuer(x,mid,r,ind*2+2));
            }
        }
        double quer(double x){
            return realQuer(x,0,n,0);
        }
        void realUpdate(int s, int e, line nw, int ind){
            int mid = (s+e)/2;
            bool lef = st[ind].eval(s) > nw.eval(s);
            bool mi = st[ind].eval(mid) > nw.eval(mid);
            if(mi){
                swap(st[ind],nw);
            }
            if(e-s==1){
                return;
            }
            else if(lef!=mi){
                realUpdate(s,mid,nw,ind*2+1);
            }
            else{
                realUpdate(mid,e,nw,ind*2+2);
            }
        }
        void addLine(line l){
            realUpdate(0,n,l,0);
        }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    long long h[n],w[n];
    long long tot = 0;
    for(long long i = 0;i<n;i++){
        cin >> h[i];
    }
    for(long long i = 0;i<n;i++){
        cin >> w[i];
        tot+=w[i];
    }
    long long dp[n];
    dp[0]=-w[0];
    liChaoTree<long long> lct(2e6+50);
    for(long long i = 1;i<n;i++){
        line l;
        l.m=-2*h[i-1];
        l.c=dp[i - 1] + h[i - 1] * h[i - 1];
        lct.addLine(l);
        dp[i]=lct.quer(h[i]) - w[i]+h[i]*h[i];
    }
    cout << tot+dp[n-1];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65884 KB Output is correct
2 Correct 24 ms 65884 KB Output is correct
3 Correct 24 ms 65884 KB Output is correct
4 Correct 24 ms 66028 KB Output is correct
5 Correct 24 ms 66140 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 68444 KB Output is correct
2 Correct 68 ms 68432 KB Output is correct
3 Correct 68 ms 68436 KB Output is correct
4 Correct 59 ms 68436 KB Output is correct
5 Incorrect 53 ms 68432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 65884 KB Output is correct
2 Correct 24 ms 65884 KB Output is correct
3 Correct 24 ms 65884 KB Output is correct
4 Correct 24 ms 66028 KB Output is correct
5 Correct 24 ms 66140 KB Output is correct
6 Correct 63 ms 68444 KB Output is correct
7 Correct 68 ms 68432 KB Output is correct
8 Correct 68 ms 68436 KB Output is correct
9 Correct 59 ms 68436 KB Output is correct
10 Incorrect 53 ms 68432 KB Output isn't correct
11 Halted 0 ms 0 KB -