oj.uz

Submission #237802

# Submission time Handle Problem Language Result Execution time Memory
237802 2020-06-08T20:16:50 Z DS007 Building Bridges (CEOI17_building) C++14
100 / 100
 93 ms 66552 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5, H = 1e6 + 5;

class Line {
public:
    int m, c;

    Line() {
        m = 0;
        c = 1e18;
    }

    Line(int m_, int c_) {
        m = m_;
        c = c_;
    }

    int evaluate(int x) {
        return m * x + c;
    }
};

class LiChaoTree {
    Line *t;
    int n;

public:
    LiChaoTree(int n_) {
        n = n_;
        t = new Line[n * 4];
    }

    int insert(int v, int l, int r, Line nl) {
        if (l + 1 == r)
            return t[v] = nl.evaluate(l) < t[v].evaluate(l) ? nl : t[v], 1;

        int mid = (l + r) / 2;
        if (t[v].m > nl.m) swap(t[v], nl);
        if (t[v].evaluate(mid) > nl.evaluate(mid))
            swap(t[v], nl), insert(v * 2 + 1, mid, r, nl);
        else
            insert(v * 2, l, mid, nl);
    }

    int query(int v, int l, int r, int x) {
        if (l + 1 == r)
            return t[v].evaluate(x);

        int mid = (l + r) / 2;
        if (x < mid)
            return min(t[v].evaluate(x), query(v * 2, l, mid, x));
        else
            return min(t[v].evaluate(x), query(v * 2 + 1, mid, r, x));
    }
};

int h[N], w[N], dp[N];
int n, s;

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> w[i], s += w[i];

    LiChaoTree lct(H);
    dp[0] = -w[0];
    lct.insert(1, 0, H, Line(-2 * h[0], dp[0] + h[0] * h[0]));

    for (int i = 1; i < n; i++)
        dp[i] = lct.query(1, 0, H, h[i]) + h[i] * h[i] - w[i], lct.insert(1, 0, H, Line(-2 * h[i], dp[i] + h[i] * h[i]));

    cout << dp[n - 1] + s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message

building.cpp: In function 'long long int solveTestCase()':
building.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
building.cpp: In member function 'long long int LiChaoTree::insert(long long int, long long int, long long int, Line)':
building.cpp:46:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62968 KB Output is correct
2 Correct 35 ms 62968 KB Output is correct
3 Correct 35 ms 62972 KB Output is correct
4 Correct 35 ms 63104 KB Output is correct
5 Correct 40 ms 63096 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 66292 KB Output is correct
2 Correct 82 ms 66296 KB Output is correct
3 Correct 83 ms 66296 KB Output is correct
4 Correct 83 ms 66236 KB Output is correct
5 Correct 82 ms 66296 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62968 KB Output is correct
2 Correct 35 ms 62968 KB Output is correct
3 Correct 35 ms 62972 KB Output is correct
4 Correct 35 ms 63104 KB Output is correct
5 Correct 40 ms 63096 KB Output is correct
6 Correct 82 ms 66292 KB Output is correct
7 Correct 82 ms 66296 KB Output is correct
8 Correct 83 ms 66296 KB Output is correct
9 Correct 83 ms 66236 KB Output is correct
10 Correct 82 ms 66296 KB Output is correct
11 Correct 93 ms 66552 KB Output is correct
12 Correct 89 ms 66296 KB Output is correct
13 Correct 84 ms 66424 KB Output is correct
14 Correct 88 ms 66424 KB Output is correct
15 Correct 88 ms 66168 KB Output is correct
16 Correct 83 ms 66296 KB Output is correct
17 Correct 62 ms 66424 KB Output is correct
18 Correct 68 ms 66424 KB Output is correct