oj.uz

Submission #123841

# Submission time Handle Problem Language Result Execution time Memory
123841 2019-07-02T07:49:02 Z FutymyClone Building Bridges (CEOI17_building) C++14
100 / 100
 135 ms 66532 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long inf = 1LL << 62;
const int maxn = 1e6 + 5;

int n, h[N], w[N];
long long dp[N], f[N];

struct Line {
    int a;
    long long b;
    Line (int a = 0, long long b = inf): a(a), b(b) {}
    long long f (int x) {
        return 1LL * a * x + b;
    }
} node[maxn << 2];

struct LiChaoTree {
    void add (int i, int l, int r, Line val) {
        if (node[i].f(l) >= val.f(l) && node[i].f(r) >= val.f(r)) {
            node[i] = val;
            return;
        }

        if (node[i].f(l) <= val.f(l) && node[i].f(r) <= val.f(r)) return;

        int mid = l + r >> 1;
        add(i << 1, l, mid, val);
        add(i << 1 | 1, mid + 1, r, val);
    }

    long long query (int i, int l, int r, int x) {
        if (l == r) return node[i].f(x);

        int mid = l + r >> 1;
        if (x <= mid) return min(node[i].f(x), query(i << 1, l, mid, x));
        return min(node[i].f(x), query(i << 1 | 1, mid + 1, r, x));
    }
} lct;

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] + w[i];

    //dp(i) = max(dp(j) + f(i - 1) - f(j) + hi^2 + hj^2 - 2hihj | j < i)
    //dp(i) = max(-2hjhi + hj^2 + dp(j) - f(j) + f(i - 1) + hi^2 | j < i)
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    lct.add(1, 0, maxn - 1, Line(-2 * h[1], 1LL * h[1] * h[1] + dp[1] - f[1]));
    for (int i = 2; i <= n; i++) {
        dp[i] = lct.query(1, 0, maxn - 1, h[i]) + f[i - 1] + 1LL * h[i] * h[i];
        lct.add(1, 0, maxn - 1, Line(-2 * h[i], 1LL * h[i] * h[i] + dp[i] - f[i]));
    }

    printf("%lld", dp[n]);
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message

building.cpp: In member function 'void LiChaoTree::add(int, int, int, Line)':
building.cpp:30:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
building.cpp: In member function 'long long int LiChaoTree::query(int, int, int, int)':
building.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
building.cpp: In function 'int main()':
building.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:46:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
                                  ~~~~~^~~~~~~~~~~~~
building.cpp:47:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 54 ms 63708 KB Output is correct
3 Correct 57 ms 63676 KB Output is correct
4 Correct 54 ms 63736 KB Output is correct
5 Correct 53 ms 63736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 65340 KB Output is correct
2 Correct 135 ms 66360 KB Output is correct
3 Correct 125 ms 66384 KB Output is correct
4 Correct 117 ms 66168 KB Output is correct
5 Correct 111 ms 66168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63736 KB Output is correct
2 Correct 54 ms 63708 KB Output is correct
3 Correct 57 ms 63676 KB Output is correct
4 Correct 54 ms 63736 KB Output is correct
5 Correct 53 ms 63736 KB Output is correct
6 Correct 128 ms 65340 KB Output is correct
7 Correct 135 ms 66360 KB Output is correct
8 Correct 125 ms 66384 KB Output is correct
9 Correct 117 ms 66168 KB Output is correct
10 Correct 111 ms 66168 KB Output is correct
11 Correct 127 ms 66424 KB Output is correct
12 Correct 131 ms 66420 KB Output is correct
13 Correct 103 ms 66424 KB Output is correct
14 Correct 130 ms 66532 KB Output is correct
15 Correct 110 ms 66168 KB Output is correct
16 Correct 110 ms 66280 KB Output is correct
17 Correct 81 ms 66296 KB Output is correct
18 Correct 80 ms 66424 KB Output is correct