oj.uz

답안 #870815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870815 2023-11-09T08:08:19 Z paduc Building Bridges (CEOI17_building) C++17
100 / 100
 43 ms 71372 KB 
/*
                   /\ \    /\ \
 _____      __     \_\ \   \_\ \  __  __  __  __  __    ___    ____
/\ '__`\  /'__`\   /'_` \  /'_` \/\ \/\ \/\ \/\ \/\ \  /'___\ /',__\
\ \ \L\ \/\ \L\.\_/\ \L\ \/\ \L\ \ \ \_\ \ \ \_/ \_/ \/\ \__//\__, `\
 \ \ ,__/\ \__/.\_\ \___,_\ \___,_\ \____/\ \___x___/'\ \____\/\____/
  \ \ \/  \/__/\/_/\/__,_ /\/__,_ /\/___/  \/__//__/   \/____/\/___/
   \ \_\                 ____________________
    \/_/                /nowl/
*/
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ull unsigned long long
#define ll long long
#define ld double
#define yes {cout << "YES"; return;}
#define no {cout << "NO"; return;}
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using pii = pair<int,int>;
constexpr int mod = 1e9 + 7;
constexpr ll oo = 1e18;
constexpr ld eps = 1e-9;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define fi first
#define se second
#define name "pad"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

template<typename T> bool maximize(T &a, T b) { return a < b && (a = b, true); }
template<typename T> bool minimize(T &a, T b) { return a > b && (a = b, true); }
template<typename T> void compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

struct line{
    int a, b;
    line(int _a = 0, int _b = inf) { a = _a; b = _b; }
    int operator() (int x) { return a * x + b; }
};

struct LiChaoTree{
    vector<line> st; int n, Left, Right;

    LiChaoTree(int _n = 0, int _Left = 0, int _Right = 0) {
        n = _n; Left = _Left; Right = _Right;
        st.resize(n * 4 + 5);
    }

    void update(int id, int l, int r, line d) {

        if(st[id](l) >= d(l) && st[id](r) >= d(r)) {
            st[id] = d;
            return;
        }

        if(st[id](l) <= d(l) && st[id](r) <= d(r)) {
            return;
        }

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

        if(st[id](l) >= d(l) && st[id](m) >= d(m)) {
            update(id * 2 + 1, m + 1, r, st[id]);
            st[id] = d;
            return;
        }

        if(st[id](l) <= d(l) && st[id](m) <= d(m)) {
            update(id * 2 + 1, m + 1, r, d);
            return;
        }

        if(st[id](m + 1) >= d(m + 1) && st[id](r) >= d(r)) {
            update(id * 2, l, m, st[id]);
            st[id] = d;
            return;
        }

        if(st[id](m + 1) <= d(m + 1) && st[id](r) <= d(r)) {
            update(id * 2, l, m, d);
            return;
        }

    }
    void update(line d) {
        update(1, Left, Right, d);
    }

    int get(int id, int l, int r, int p) {
        int res = st[id](p);
        while(l != r) {
            int m = (l + r) >> 1;
            if(m >= p) id = id * 2, r = m, minimize(res, st[id](p));
            else id = id * 2 + 1, l = m + 1, minimize(res, st[id](p));
        }
        return res;
    }
    int get(int p) {
        return get(1, Left, Right, p);
    }

};

const int N = 1e6 + 5;
int n, h[N], w[N], f[N], sum = 0;

int32_t main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
//    freopen(name".inp", "r", stdin);
//    freopen(name".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], sum += w[i];

    LiChaoTree tom(N, 0, 1e6);

    f[1] = -w[1];
    tom.update(line(-2 * h[1], h[1] * h[1] + f[1]));

    for(int i = 2; i <= n; ++i) {
        f[i] = tom.get(h[i]) - w[i] + h[i] * h[i];
        tom.update(line(-2 * h[i], h[i] * h[i] + f[i]));
    }

    cout << f[n] + sum;

    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 67164 KB Output is correct
2 Correct 10 ms 67072 KB Output is correct
3 Correct 11 ms 67164 KB Output is correct
4 Correct 10 ms 67164 KB Output is correct
5 Correct 11 ms 67160 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 71368 KB Output is correct
2 Correct 43 ms 71248 KB Output is correct
3 Correct 39 ms 71260 KB Output is correct
4 Correct 37 ms 71252 KB Output is correct
5 Correct 34 ms 71248 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 67164 KB Output is correct
2 Correct 10 ms 67072 KB Output is correct
3 Correct 11 ms 67164 KB Output is correct
4 Correct 10 ms 67164 KB Output is correct
5 Correct 11 ms 67160 KB Output is correct
6 Correct 41 ms 71368 KB Output is correct
7 Correct 43 ms 71248 KB Output is correct
8 Correct 39 ms 71260 KB Output is correct
9 Correct 37 ms 71252 KB Output is correct
10 Correct 34 ms 71248 KB Output is correct
11 Correct 40 ms 71252 KB Output is correct
12 Correct 41 ms 71272 KB Output is correct
13 Correct 33 ms 71248 KB Output is correct
14 Correct 41 ms 71256 KB Output is correct
15 Correct 36 ms 71248 KB Output is correct
16 Correct 34 ms 71252 KB Output is correct
17 Correct 24 ms 71256 KB Output is correct
18 Correct 25 ms 71372 KB Output is correct