oj.uz

Submission #1001058

# Submission time Handle Problem Language Result Execution time Memory
1001058 2024-06-18T13:54:08 Z nngan267 Building Bridges (CEOI17_building) C++17
100 / 100
 80 ms 12880 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pll pair<ll, ll>
#define vi vector<int>
#define db long double

const int maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1e18+7;
const double eps = 1e-9;
const double pi = acos(-1);
const int block_size = 320;

int n, h[maxn], w[maxn];
ll s[maxn];
ll dp[maxn];

struct Line{
    bool t;
    db x;
    ll a, b;

    bool operator < (const Line &l) const{
        if(t || l.t) return x < l.x;
        return a > l.a;
    }
};

struct linecontainer{
    set<Line> cht;

    bool has_prev(set<Line>::iterator it) {return it != cht.begin();}
    bool has_next(set<Line>::iterator it) {return it != cht.end() && next(it) != cht.end();}

    db intersect(set<Line>::iterator l1, set<Line>::iterator l2){
        return (double) (l2->b - l1->b) / (l1->a - l2->a);
    }

    void cal_x(set<Line>::iterator it){
        if(has_prev(it)){
            Line l = *it;
            l.x = intersect(prev(it), it);
            cht.insert(cht.erase(it), l);
        }
    }

    bool bad(set<Line>::iterator it){
        return has_prev(it) && has_next(it) && (intersect(prev(it), next(it)) <= intersect(prev(it), it));
    }

    void add(ll a, ll b){
        set<Line>::iterator it;
        it = cht.lower_bound({0, 0, a, b});
        if(it != cht.end() && it->a == a){
            if(it->b >= b) cht.erase(it);
            else return;
        }
        it = cht.insert({0, 0, a, b}).first;
        if(bad(it)) cht.erase(it);
        else{
            while(has_prev(it) && bad(prev(it))) cht.erase(prev(it));
            while(has_next(it) && bad(next(it))) cht.erase(next(it));
            if(has_next(it)) cal_x(next(it));
            cal_x(it);
        }
    }

    ll query(ll x){
        Line l = *prev(cht.upper_bound({1, (double)x, 0, 0}));
        return l.a * x + l.b;
    }
};

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> h[i];
    }
    for(int i=1; i<=n; i++){
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }
    linecontainer cht;
    ll a = -2*h[1];
    ll b = 1ll*h[1]*h[1] - s[1];
    cht.add(a, b);
    for(int i=2; i<=n; i++){
        dp[i] = cht.query(h[i]) + 1ll*h[i]*h[i] + s[i-1];
        a = -2*h[i];
        b = dp[i] + 1ll*h[i]*h[i] - s[i];
        cht.add(a, b);
    }
    cout << dp[n] << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
//    cin >> test;
    while(test--){
        solve();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3920 KB Output is correct
2 Correct 53 ms 3928 KB Output is correct
3 Correct 57 ms 3760 KB Output is correct
4 Correct 48 ms 3632 KB Output is correct
5 Correct 47 ms 5576 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 53 ms 3920 KB Output is correct
7 Correct 53 ms 3928 KB Output is correct
8 Correct 57 ms 3760 KB Output is correct
9 Correct 48 ms 3632 KB Output is correct
10 Correct 47 ms 5576 KB Output is correct
11 Correct 45 ms 3928 KB Output is correct
12 Correct 52 ms 3824 KB Output is correct
13 Correct 32 ms 3756 KB Output is correct
14 Correct 49 ms 3912 KB Output is correct
15 Correct 80 ms 12880 KB Output is correct
16 Correct 48 ms 5460 KB Output is correct
17 Correct 18 ms 3672 KB Output is correct
18 Correct 11 ms 3636 KB Output is correct