Submission #468526

#	Time	Username	Problem	Language	Result	Execution time	Memory
468526		idk321	Building Bridges (CEOI17_building)	C++17	60 / 100	249 ms	16000 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1000000000000000006LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<ll> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    vector<ll> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    if (n <= 1000) {
        vector<ll> dp(n, INF);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            ll cost = 0;
            for (int j = i - 1; j >= 0; j--) {
                dp[i] = min(dp[i], dp[j] + cost + (h[i] - h[j]) *  (h[i] - h[j]));
                cost += w[j];
            }
        }
        cout << dp[n - 1] << "\n";
    } else {
        ll res = 0;
        ll sumAll = 0;
        for (int i = 1; i < n - 1; i++) sumAll += w[i];
        res += (h[n - 1] - h[0]) * (h[n - 1] - h[0]) + sumAll;

        for (int i = 1; i < n - 1; i++) {
            res = min(res, sumAll - w[i] + (h[i] - h[0]) * (h[i] - h[0]) + (h[n - 1] - h[i]) * (h[n - 1] - h[i]));
        }

        map<int, multiset<int>> byHeight;
        for (int i = 1; i < n - 1; i++) {
            byHeight[h[i]].insert(w[i]);
        }
        for (int i = 1; i < n - 2; i++) {
            byHeight[h[i]].erase(byHeight[h[i]].find(w[i]));
            if (byHeight[h[i]].empty()) byHeight.erase(h[i]);

            ll cur = sumAll - w[i] + (h[i] - h[0]) * (h[i] - h[0]);
            auto it = byHeight.lower_bound((h[n - 1] + h[i]) / 2);
            int first = -1;
            while (it != byHeight.end()) {
                ll cur2 = cur + (h[i] -  it->first) * (h[i] -  it->first) + (h[n - 1] - it->first) * (h[n - 1] - it->first)  - *(it->second).rbegin();
                res = min(res, cur2);
                if (first == -1) first = it->first;
                else if (it->first - first > 10) break;
                it++;
            }

            it = byHeight.lower_bound((h[n - 1] + h[i]) / 2);
            if (it == byHeight.begin()) continue;
            first = -1;
            it--;
            while (true) {
                ll cur2 = cur + (h[i] -  it->first) * (h[i] -  it->first) + (h[n - 1] - it->first) * (h[n - 1] - it->first)  - *(it->second).rbegin();
                res = min(res, cur2);
                if (first == -1) first = it->first;
                else if (first - it->first > 10) {
                    break;
                }
                if (it == byHeight.begin()) break;
                it--;
            }
        }

        cout << res << "\n";
    }

}

/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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