Submission #1169840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169840		icebear	Building Bridges (CEOI17_building)	C++20	100 / 100	48 ms	65352 KiB

building

// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;

class LiChao {
private:
    struct Line {
        ll a, b;
        Line (ll _a = 0, ll _b = INF): a(_a), b(_b) {}

        ll eval(ll x) {
            return (b == INF ? INF : a * x + b);
        }
        ll slope() {
            return a;
        }
    };

    int MAX;
    vector<Line> node;

    void update(int id, int l, int r, Line newL) {
        if (l == r) {
            node[id] = (newL.eval(l) < node[id].eval(l) ? newL : node[id]);
            return;
        }

        int mid = (l + r) >> 1;
        if (newL.eval(mid) < node[id].eval(mid)) swap(newL, node[id]);

        if (newL.slope() > node[id].slope())
            update(id << 1, l, mid, newL);
        if (newL.slope() < node[id].slope())
            update(id << 1 | 1, mid + 1, r, newL);
    }

    ll get(int id, int l, int r, int pos) {
        ll cur = node[id].eval(pos);
        int mid = (l + r) >> 1;

        if (l == r) return cur;
        if (pos <= mid)
            return min(cur, get(id << 1, l, mid, pos));
        return min(cur, get(id << 1 | 1, mid + 1, r, pos));
    }

public:
    LiChao(int _MAX = 0): MAX(_MAX), node(_MAX * 4 + 5, Line(0, INF)) {}

    void addLine(ll a, ll b) {
        update(1, 1, MAX, Line(a, b));
    }

    ll query(int pos) {
        return get(1, 1, MAX, pos);
    }
} lichao;

int n, h[N], w[N], MAX_HEIGHT;
ll pref[N], dp[N];

void init(void) {
    cin >> n;
    FOR(i, 1, n) cin >> h[i], maximize(MAX_HEIGHT, h[i]);
    FOR(i, 1, n) cin >> w[i], pref[i] = pref[i - 1] + w[i];
}

void process(void) {
    lichao = LiChao(MAX_HEIGHT);
    FOR(i, 1, n) {
        if (i > 1)
            dp[i] = 1LL * h[i] * h[i] + pref[i - 1] + lichao.query(h[i]);
        lichao.addLine(-2 * h[i], dp[i] - pref[i] + 1LL * h[i] * h[i]);
    }

    cout << dp[n];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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