Submission #1024166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024166		_callmelucian	Building Bridges (CEOI17_building)	C++14	100 / 100	71 ms	66640 KiB

building

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40