oj.uz

Submission #859113

# Submission time Handle Problem Language Result Execution time Memory
859113 2023-10-09T18:00:19 Z ThegeekKnight16 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 5544 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;
    }

    SparseSeg() {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)
    {
        if (ini == fim)
        {
            seg[pos] = (seg[pos](ini) < val(ini) ? seg[pos] : val);
            return;
        }
        int m = (ini + fim) >> 1;
        if (seg[pos].l < val.l) swap(seg[pos], val);
        if (seg[pos](m) < val(m)) update(getRight(pos), m+1, fim, val);
        else swap(seg[pos], val), update(getLeft(pos), ini, m, val);
    }

    int query(int pos, int ini, int fim, int id)
    {
        if (ini == fim) 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;

    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]);
        for (int j = 1; j < i; j++)
        {
            dp[i] = min(dp[i], dp[j] + sw[i-1] - sw[j] + ((h[i] - h[j])*(h[i] - h[j])));
        }
        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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 600 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 5544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Execution timed out 3035 ms 5544 KB Time limit exceeded
7 Halted 0 ms 0 KB -