Submission #1184781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184781		misavo	Building Bridges (CEOI17_building)	C++20	100 / 100	36 ms	9032 KiB

building

#include <bits/stdc++.h>
// #include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << " " <<endl;
#define printp(a) for(auto x : a) cout << x.first << " " << x.second <<endl;
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, k, a, b, tot;
string s;
ll h[100009], w[100009], dp[100009];

ll applyFun(pll f, ll x) { 
    return f.x*x + f.y; 
}

struct node {
    ll a, b;
    node *l, *r;
    pll f;

    node(ll x, ll y, pll g) {
        a = x; b = y;
        f = g;
        l = r = nullptr;
    }

    void addLine(pll g) {
        if (applyFun(g, (a+b)/2) < applyFun(f, (a+b)/2)) swap(f, g);
        
        if (a == b-1) return;

        if (applyFun(g, a) < applyFun(f, a)) {
            if (l == nullptr) l = new node(a, (a+b)/2, g);
            else l->addLine(g);
        } 
        if (applyFun(g, b) < applyFun(f, b)) {
            if (r == nullptr) r = new node((a+b)/2, b, g);
            else r->addLine(g);
        }
    }

    ll query(ll x) {
        if (x < (a+b)/2)
            return l ? min(l->query(x), applyFun(f, x)) : applyFun(f, x);
        else
            return r ? min(r->query(x), applyFun(f, x)) : applyFun(f, x);
    }
};

void solve() {
    cin >> n;
    cf(i, 1, n) cin >> h[i];
    cf(i, 1, n) {
        cin >> w[i];
        dp[n] += w[i];
    }

    dp[n] -= w[n];
    node tree(0, 1e6, {-2*h[n], (h[n] * h[n]) + dp[n]});
    rf(i, n-1, 1) {
        dp[i] = tree.query(h[i]) + (h[i] * h[i]) - w[i];
        tree.addLine({-2*h[i], (h[i] * h[i]) + dp[i]});
    } cout << dp[1] <<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    t = 1;
    while (t--) {
        solve();
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40