oj.uz

Submission #1086201

# Submission time Handle Problem Language Result Execution time Memory
1086201 2024-09-09T17:43:58 Z serifefedartar Building Bridges (CEOI17_building) C++17
100 / 100
 75 ms 65728 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 100;

#define int long long
struct Line {
    int m, c;
    int eval(int x) {
        return m * x + c;
    }
 
    Line() : m(0), c(10000000000000000LL) { }
    Line(int _m, int _c) : m(_m), c(_c) { }
};

vector<int> h, w;
Line sg[4*MAXN];

void add_line(int k, int l, int r, Line new_line) {
    if (l == r) {
        if (new_line.eval(l) < sg[k].eval(l))
            sg[k] = new_line;
        return ;
    }
 
    int mid = (l + r) / 2;
    if (sg[k].m > new_line.m)
        swap(sg[k], new_line);
    if (sg[k].eval(mid) > new_line.eval(mid)) {
        swap(sg[k], new_line);
        add_line(2*k+1, mid+1, r, new_line);
    } else
        add_line(2*k, l, mid, new_line);
}

int get(int k, int l, int r, int x) {
    if (l == r)
        return sg[k].eval(x);
    if (x <= (l + r) / 2)
        return min(sg[k].eval(x), get(2*k, l, (l+r)/2, x));
    else
        return min(sg[k].eval(x), get(2*k+1, (l+r)/2+1, r, x));
}

signed main() {
    fast;
    int N;
    cin >> N;

    h = vector<int>(N+1, 0);
    w = vector<int>(N+1, 0);
    for (int i = 0; i < 4*MAXN; i++)
        sg[i] = Line();
    for (int i = 1; i <= N; i++)
        cin >> h[i];
    for (int i = 1; i <= N; i++) {
        cin >> w[i];
        w[i] += w[i-1];
    }

    ll ans = 0;
    add_line(1, 1, 1000000, Line(-2 * h[1], h[1] * h[1] - w[1]));
    for (int i = 2; i <= N; i++) {
        ans = h[i] * h[i] + w[i-1] + get(1, 1, 1000000, h[i]);
        add_line(1, 1, 1000000, Line(-2 * h[i], ans + h[i] * h[i] - w[i]));
    }
    cout << ans << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63060 KB Output is correct
2 Correct 28 ms 63064 KB Output is correct
3 Correct 28 ms 63068 KB Output is correct
4 Correct 27 ms 63056 KB Output is correct
5 Correct 27 ms 63064 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 65616 KB Output is correct
2 Correct 57 ms 65564 KB Output is correct
3 Correct 61 ms 65616 KB Output is correct
4 Correct 58 ms 65364 KB Output is correct
5 Correct 54 ms 65360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 63060 KB Output is correct
2 Correct 28 ms 63064 KB Output is correct
3 Correct 28 ms 63068 KB Output is correct
4 Correct 27 ms 63056 KB Output is correct
5 Correct 27 ms 63064 KB Output is correct
6 Correct 60 ms 65616 KB Output is correct
7 Correct 57 ms 65564 KB Output is correct
8 Correct 61 ms 65616 KB Output is correct
9 Correct 58 ms 65364 KB Output is correct
10 Correct 54 ms 65360 KB Output is correct
11 Correct 69 ms 65668 KB Output is correct
12 Correct 72 ms 65652 KB Output is correct
13 Correct 61 ms 65624 KB Output is correct
14 Correct 75 ms 65652 KB Output is correct
15 Correct 54 ms 65364 KB Output is correct
16 Correct 55 ms 65580 KB Output is correct
17 Correct 53 ms 65728 KB Output is correct
18 Correct 51 ms 65544 KB Output is correct