oj.uz

Submission #1086177

# Submission time Handle Problem Language Result Execution time Memory
1086177 2024-09-09T16:45:41 Z serifefedartar Building Bridges (CEOI17_building) C++17
0 / 100
 51 ms 64604 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 (sg[k].eval(l) <= new_line.eval(l) && sg[k].eval(r) <= new_line.eval(r))
        return ;
    if (sg[k].eval(l) > new_line.eval(l) && sg[k].eval(r) > new_line.eval(r)) {
        swap(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, l, mid, new_line);
    } else
        add_line(2*k+1, mid+1, r, 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63060 KB Output is correct
2 Incorrect 27 ms 63056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 64604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63060 KB Output is correct
2 Incorrect 27 ms 63056 KB Output isn't correct
3 Halted 0 ms 0 KB -