Submission #1192009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192009		shirokito	Building Bridges (CEOI17_building)	C++20	100 / 100	55 ms	66120 KiB

building

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define el '\n'

const int N = 1e6 + 24; 
const ll INF = 4e18;

int n; ll h[N], w[N];
ll pre[N], dp[N];

struct Line {
    ll a, b;
    ll calc(ll x) { return a * x + b; }
};

struct Lichao {
    int n; vector<Line> t;

    Lichao(int sz) : t(4 * sz + 24, {0, LLONG_MAX}), n(sz) {}

    void update(int id, int l, int r, Line f) {
        if (l == r) {
            if (f.calc(l) < t[id].calc(l)) t[id] = f;
            return;
        }

        int mid = (l + r) >> 1;
        if (f.calc(mid) < t[id].calc(mid)) swap(f, t[id]);

        if (f.calc(l) < t[id].calc(l)) update(2 * id, l, mid, f);
        if (f.calc(r) < t[id].calc(r)) update(2 * id + 1, mid + 1, r, f);
    }

    ll get(int id, int l, int r, int i) {
        int mid = (l + r) >> 1;
        ll cur = t[id].calc(i);

        if (i == mid) return cur;
        else if (i < mid) return min(get(2 * id, l, mid, i), cur);
        else return min(get(2 * id + 1, mid + 1, r, i), cur);
    }
};

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i];

    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + w[i];
    }

    Lichao lct(N);

    dp[1] = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 1) dp[i] = h[i] * h[i] + pre[i - 1] + lct.get(1, 0, N, h[i]);
        lct.update(1, 0, N, {-2 * h[i], dp[i] + h[i] * h[i] - pre[i]});
    }

    cout << dp[n] << el;
}

int main() {
    cin.tie(NULL) -> sync_with_stdio(false);

    #define task "file"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; // cin >> T;
    while (T--) solve();
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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