oj.uz

Submission #468500

# Submission time Handle Problem Language Result Execution time Memory
468500 2021-08-28T15:36:18 Z idk321 Building Bridges (CEOI17_building) C++17
30 / 100
 257 ms 15920 KB 
#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 > 20) break;
                it++;
            }

            it = byHeight.lower_bound((h[n - 1] + h[i]) / 2);
            if (it == byHeight.begin()) break;
            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 > 20) {
                    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 7320 KB Output is correct
2 Correct 248 ms 7240 KB Output is correct
3 Correct 257 ms 7260 KB Output is correct
4 Correct 193 ms 6736 KB Output is correct
5 Incorrect 56 ms 15920 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 257 ms 7320 KB Output is correct
7 Correct 248 ms 7240 KB Output is correct
8 Correct 257 ms 7260 KB Output is correct
9 Correct 193 ms 6736 KB Output is correct
10 Incorrect 56 ms 15920 KB Output isn't correct