Submission #1282237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282237		red_souls	Building Bridges (CEOI17_building)	C++20	100 / 100	39 ms	9680 KiB

building

#include <bits/stdc++.h>
#define ll long long
#define task "CEOI17_building"
using namespace std;

const int N = 1e5 + 16;
const ll INF = 1e18;
int n;
ll h[N], w[N];

namespace sub3 {

    struct line {
        ll a, b;
        mutable ll p;

        bool operator < (const line &other) const {
            if (other.a == INF && other.b == INF) {
                return p < other.p;
            }
            return a < other.a;
        }
    };

    struct lineContainer {
        multiset <line> lc;

        ll div(ll a, ll b) {
            return a / b - ((a ^ b) < 0 && a % b);
        }

        bool isSect(multiset <line> :: iterator x, multiset <line> :: iterator y) {
            if (y == lc.end()) {
                x->p = INF;
                return false;
            }

            if (x->a == y->a) {
                x->p = x->b > y->b ? INF : -INF;
            }
            else {
                x->p = div(y->b - x->b, x->a - y->a);
            }

            return x->p >= y->p;
        }

        void add(ll a, ll b) {
            auto x = lc.insert({a, b, 0}), y = next(x);
            while (isSect(x, y)) {
                y = lc.erase(y);
            }
            if ((y = x) != lc.begin() && isSect(--y, x)) {
                isSect(y, lc.erase(x));
            }
            while ((x = y) != lc.begin() && (--x)->p >= y->p) {
                isSect(x, lc.erase(y));
                y = x;
            }
        }

        ll query(ll x) {
            line l = *lc.lower_bound({INF, INF, x});
            return l.a * x + l.b;
        }
    };

    lineContainer cht;

    ll dp[N], prefix[N];

    void solve() {

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

        for (int i = 1; i <= n; i++) {
            dp[i] = INF;
        }
        dp[1] = 0;
        cht.add(-(-2 * h[1]), -(dp[1] - prefix[1] + h[1] * h[1]));
        for (int i = 2; i <= n; i++) {
            dp[i] = -cht.query(h[i]) + h[i] * h[i] + prefix[i - 1];
            cht.add(-(-2 * h[i]), -(dp[i] - prefix[i] + h[i] * h[i]));
        }

        cout << dp[n];
    }
}

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

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

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

    return 0;
}

Compilation message (stderr)

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

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