oj.uz

Submission #561990

# Submission time Handle Problem Language Result Execution time Memory
561990 2022-05-14T03:30:14 Z abcvuitunggio Building Bridges (CEOI17_building) C++17
0 / 100
 40 ms 3620 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define point pair <int, int>
#define fi first
#define se second
#define int long long
typedef long double ld;
using namespace std;
int n,m,dp[100001],h[100001],w[100001],c,last,sumw;
vector <point> v[18],ve[18];
bool cmp(point a, point b){
    if (a.fi!=b.fi)
        return a.fi<b.fi;
    return a.se>b.se;
}
int ce(int a, int b){
    return a/b+(a*b>0&&a/b*b!=a);
}
ld intersection(pair <int, int> p, pair <int, int> p2){
    return ((ld)(p2.se-p.se))/(p.fi-p2.fi);
}
void add(pair <int, int> p, int idx){
    if (!v[idx].empty()&&v[idx].back().fi==p.fi)
        return;
    while (v[idx].size()>1){
        ld p12=intersection(v[idx][v[idx].size()-2],v[idx].back()),p13=intersection(v[idx][v[idx].size()-2],p);
        if (p12<p13)
            break;
        v[idx].pop_back();
        if (!ve[idx].empty())
            ve[idx].pop_back();
    }
    if (!v[idx].empty())
        ve[idx].push_back({ce(p.se-v[idx].back().se,v[idx].back().fi-p.fi),v[idx].size()});
    v[idx].push_back(p);
}
int get(int x, int idx){
    int l=0,r=((int)ve[idx].size())-1,kq=0;
    while (l<=r){
        int mid=(l+r)>>1;
        if (ve[idx][mid].fi<=x){
            kq=ve[idx][mid].se;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return -v[idx][kq].fi*x-v[idx][kq].se;
}
void add2(point p){
    vector <point> vp;
    vp.push_back(p);
    int j=0;
    while (!v[j].empty()){
        for (auto i:v[j])
            vp.push_back(i);
        v[j].clear();
        ve[j].clear();
        j++;
    }
    last=j;
    sort(vp.begin(),vp.end(),cmp);
    for (auto i:vp)
        add(i,j);
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> h[i];
    for (int i=1;i<=n;i++){
        cin >> w[i];
        sumw+=w[i];
    }
    dp[1]=-w[1];
    for (int i=1;i<n;i++){
        add2({h[i]*2,-dp[i]-h[i]*h[i]});
        dp[i+1]=get(h[i+1],last)-w[i+1]+h[i+1]*h[i+1];
    }
    cout << dp[n]+sumw;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 3620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -