Submission #860141

#	Time	Username	Problem	Language	Result	Execution time	Memory
860141		ThegeekKnight16	Building Bridges (CEOI17_building)	C++17	100 / 100	37 ms	12232 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int border = 1e6 + 10;
struct Line
{
    int l, b;
    Line(int L = 0, int B = 0) : l(L), b(B) {}

    int operator()(int x) {return l * x + b;}
};
class SparseSeg
{
protected:
    vector<Line> seg;
    vector<int> e, d;
public:
    int create()
    {
        seg.emplace_back(0, INF);
        e.push_back(0);
        d.push_back(0);
        return seg.size()-1;
    }

    void init()
    {
        seg.clear(); e.clear(); d.clear();
        create(); create();
    }

    int getLeft(int pos)
    {
        if (e[pos] == 0) {int aux = create(); e[pos] = aux;}
        return e[pos];
    }

    int getRight(int pos)
    {
        if (d[pos] == 0) {int aux = create(); d[pos] = aux;}
        return d[pos];
    }

    void update(int pos, int ini, int fim, Line val)
    {
        int m = (ini + fim) >> 1;
        if (val(m) < seg[pos](m)) swap(seg[pos], val);

        if (ini == fim) return;

        if (val(ini) < seg[pos](ini)) update(getLeft(pos), ini, m, val);
        else update(getRight(pos), m+1, fim, val);
    }

    int query(int pos, int ini, int fim, int id)
    {
        if (ini == fim || pos == 0) return seg[pos](ini);
        int m = (ini + fim) >> 1;
        if (id <= m) return min(seg[pos](id), query(e[pos], ini, m, id));
        else return min(seg[pos](id), query(d[pos], m+1, fim, id));
    }
};

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> h(N+1, 0), w(N+1, 0), dp(N+1, 0), sw(N+1);
    for (int i = 1; i <= N; i++) cin >> h[i];
    for (int i = 1; i <= N; i++) cin >> w[i];

    for (int i = 1; i <= N; i++) sw[i] = sw[i-1] + w[i];

    SparseSeg seg;
    seg.init();

    dp[1] = 0;
    seg.update(1, 0, border, Line(-2*h[1], h[1]*h[1] - w[1]));
    for (int i = 2; i <= N; i++)
    {
        dp[i] = h[i]*h[i] + sw[i-1] + seg.query(1, 0, border, h[i]);
        seg.update(1, 0, border, Line(-2*h[i], dp[i] + h[i]*h[i] - sw[i]));
    }
    cout << dp[N] << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40