Submission #1344404

#TimeUsernameProblemLanguageResultExecution timeMemory
1344404nghiaxtoneriBuilding Bridges (CEOI17_building)C++20
100 / 100
42 ms66184 KiB
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define MASK(n) (1LL << n)
#define PhTrNghia "Building_Brides"

using namespace std;

const int maxn = 2e5 + 5;
const int inf = 1e18;

int n;
int h[maxn], w[maxn], pre[maxn], dp[maxn];

struct lichao_tree{
    int n;
    vector <pair<int, int>> tree;

    lichao_tree(int _n){
        n = _n;
        tree.assign(n << 2 | 5, {0, inf});
    }

    int get_val(pair<int, int> p, int x){
        return p.first * x + p.second;
    }

    void add(int id, int l, int r, pair <int, int> line){
        if (r - l == 1){
            if (get_val(line, l) < get_val(tree[id], l)) swap(tree[id], line);
            return;
        }

        int mid = (l + r) >> 1;

        if (get_val(line, mid) < get_val(tree[id], mid)) swap(tree[id], line);

        if (get_val(tree[id], l) < get_val(line, l)) add(id << 1 | 1, mid, r, line); else add(id << 1, l, mid, line);
    }

    int get(int id, int l, int r, int x){
        int res = get_val(tree[id], x);
        if (r - l == 1) return res;

        int mid = (l + r) >> 1;

        if (x < mid) return min(res, get(id << 1, l, mid, x)); else return min(res, get(id << 1 | 1, mid, r, x));
    }

    void add(pair<int,int> line){
        add(1, 0, n, line);
    }

    int get(int x){
        return get(1, 0, n, x);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if (fopen(PhTrNghia".INP", "r")){
        freopen(PhTrNghia".INP", "r", stdin);
        freopen(PhTrNghia".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];
        pre[i] = pre[i-1] + w[i];
    }

    int mx = 0;
    for (int i = 1; i <= n; i++) mx = max(mx, h[i]);

    lichao_tree lct(mx + 5);

    dp[1] = 0;

    for (int i = 2; i <= n; i++){
        pair <int, int> line;
        line.first = -2 * h[i-1];
        line.second = h[i-1]*h[i-1] - pre[i-1] + dp[i-1];

        lct.add(line);

        dp[i] = h[i]*h[i] + pre[i-1] + lct.get(h[i]);
    }

    cout << dp[n];
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(PhTrNghia".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(PhTrNghia".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...