Submission #1192012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192012		shirokito	Building Bridges (CEOI17_building)	C++20	100 / 100	56 ms	66168 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 x * a + b; } 
};

Line t[4 * N + 24];

void lchao_init() {
    for (int i = 0; i < 4 * N; i++) {
        t[i] = {0, LLONG_MAX};
    }
}

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(t[id], f);

    if (f.calc(l) < t[id].calc(l)) update(2 * id, l, mid, f);
    else 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 (mid == i) return cur;
    else if (mid > i) return min(cur, get(2 * id, l, mid, i));
    else return min(cur, get(2 * id + 1, mid + 1, r, i));
}

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];
    }

    lchao_init();

    dp[1] = 0;
    for (int i = 1; i <= n; i++) {
        if (i > 1) dp[i] = h[i] * h[i] + pre[i - 1] + get(1, 0, N, h[i]);
        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:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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