oj.uz

Submission #860141

# Submission time Handle Problem Language Result Execution time Memory
860141 2023-10-11T19:00:12 Z ThegeekKnight16 Building Bridges (CEOI17_building) C++17
100 / 100
 37 ms 12232 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4112 KB Output is correct
2 Correct 33 ms 4052 KB Output is correct
3 Correct 34 ms 4056 KB Output is correct
4 Correct 32 ms 3676 KB Output is correct
5 Correct 26 ms 7628 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 37 ms 4112 KB Output is correct
7 Correct 33 ms 4052 KB Output is correct
8 Correct 34 ms 4056 KB Output is correct
9 Correct 32 ms 3676 KB Output is correct
10 Correct 26 ms 7628 KB Output is correct
11 Correct 35 ms 4564 KB Output is correct
12 Correct 36 ms 5424 KB Output is correct
13 Correct 26 ms 3672 KB Output is correct
14 Correct 36 ms 5440 KB Output is correct
15 Correct 28 ms 12232 KB Output is correct
16 Correct 26 ms 7704 KB Output is correct
17 Correct 16 ms 3420 KB Output is correct
18 Correct 17 ms 3420 KB Output is correct