Submission #154442

#	Time	Username	Problem	Language	Result	Execution time	Memory
154442		dolphingarlic	Building Bridges (CEOI17_building)	C++14	0 / 100	34 ms	3704 KiB

building

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

set<pair<ll, ll>> lines;
ll h[100001], w[100001], tot = 0;
ll dp[100001];

bool check(ll h, pair<ll, ll> l1, pair<ll, ll> l2) {
    return (-l2.first * h + l2.second <= -l1.first * h + l1.second);
}
ll calc(ll h, pair<ll, ll> l) {
    return (-l.first * h + l.second);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) cin >> h[i];
    FOR(i, 1, n + 1) {
        cin >> w[i];
        tot += w[i];
    }

    dp[1] = -w[1];
    lines.insert({2 * h[1], dp[1] + h[1] * h[1]});
    FOR(i, 2, n + 1) {
        while (check(h[i], *lines.begin(), *next(lines.begin()))) lines.erase(lines.begin());
        dp[i] = calc(h[i], *lines.begin()) - w[i] + h[i] * h[i];
        lines.insert({2 * h[i], dp[i] + h[i] * h[i]});
    }

    cout << tot + dp[n];
    return 0;
}

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