oj.uz

Submission #1024166

# Submission time Handle Problem Language Result Execution time Memory
1024166 2024-07-15T14:30:48 Z _callmelucian Building Bridges (CEOI17_building) C++14
100 / 100
 71 ms 66640 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct line {
    ll a, b;

    line() : a(0), b(0) {}
    line (ll a, ll b) : a(a), b(b) {}

    ll calc (ll x) { return a * x + b; }

    ll slope() { return a; }
};

struct liChao {
    vector<line> tr;

    liChao() {}
    liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}

    void update (line f, int l, int r) {
        if (l > r) return;
        int mid = (l + r) >> 1;
        if (l == r) {
            tr[mid] = (f.calc(l) < tr[mid].calc(l) ? f : tr[mid]);
            return;
        }
        if (f.calc(mid) < tr[mid].calc(mid)) swap(tr[mid], f);
        if (f.slope() > tr[mid].slope())
            update(f, l, mid - 1); // case 1.1
        if (f.slope() < tr[mid].slope())
            update(f, mid + 1, r); // case 1.2
    }

    ll query (int p, int l, int r) {
        int mid = (l + r) >> 1;
        ll cur = tr[mid].calc(p);
        if (p == mid) return cur;
        if (p < mid) return min(query(p, l, mid - 1), cur);
        if (p > mid) return min(query(p, mid + 1, r), cur);
    }
};

const int M = 1e6 + 1;
ll dp[M], h[M], w[M];

ll f1 (int k) {
    return -2 * h[k];
}

ll f2 (int k) {
    return dp[k] + h[k] * h[k] - w[k];
}

ll f3 (int k) {
    return h[k] * h[k] + w[k - 1];
}

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

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i] += w[i - 1];
    }

    liChao tree(M);
    tree.update(line(f1(1), f2(1)), 0, M);

    for (int i = 2; i <= n; i++) {
        dp[i] = tree.query(h[i], 0, M) + f3(i);
        tree.update(line(f1(i), f2(i)), 0, M);
    }
    cout << dp[n];

    return 0;
}

Compilation message

building.cpp: In member function 'll liChao::query(int, int, int)':
building.cpp:50:5: warning: control reaches end of non-void function [-Wreturn-type]
   50 |     }
      |     ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 63060 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 26 ms 63056 KB Output is correct
4 Correct 27 ms 63068 KB Output is correct
5 Correct 28 ms 63064 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66340 KB Output is correct
2 Correct 57 ms 66384 KB Output is correct
3 Correct 59 ms 66304 KB Output is correct
4 Correct 58 ms 66132 KB Output is correct
5 Correct 57 ms 66132 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 63060 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 26 ms 63056 KB Output is correct
4 Correct 27 ms 63068 KB Output is correct
5 Correct 28 ms 63064 KB Output is correct
6 Correct 60 ms 66340 KB Output is correct
7 Correct 57 ms 66384 KB Output is correct
8 Correct 59 ms 66304 KB Output is correct
9 Correct 58 ms 66132 KB Output is correct
10 Correct 57 ms 66132 KB Output is correct
11 Correct 71 ms 66640 KB Output is correct
12 Correct 65 ms 66212 KB Output is correct
13 Correct 56 ms 66400 KB Output is correct
14 Correct 63 ms 66400 KB Output is correct
15 Correct 57 ms 66176 KB Output is correct
16 Correct 58 ms 66388 KB Output is correct
17 Correct 41 ms 66392 KB Output is correct
18 Correct 37 ms 66384 KB Output is correct