oj.uz

Submission #370628

# Submission time Handle Problem Language Result Execution time Memory
370628 2021-02-24T09:47:03 Z arujbansal Building Bridges (CEOI17_building) C++17
100 / 100
 84 ms 66540 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long

const int MXN = 1e6 + 5, INF = 1e17;
int N;

struct Line {
    int m, c;

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

    Line() {
        m = 0;
        c = INF;
    }

    Line(int m, int c) : m(m), c(c) {}
};

Line tree[4 * MXN];

void add_line(int i, int l, int r, Line line) {
    int mid = (l + r) / 2;

    if (line.val(mid) < tree[i].val(mid))
        swap(line, tree[i]);

    if (r - l <= 1) return;

    if (line.c >= INF) return;

    if (line.val(l) <= tree[i].val(l)) add_line(2 * i, l, mid, line);
    else add_line(2 * i + 1, mid + 1, r, line);
}

int query(int i, int l, int r, int x) {
    int mid = (l + r) / 2;

    int res = tree[i].val(x);

    if (r - l <= 1) return res;

    if (tree[i].c >= INF) return INF;

    if (x <= mid) return min(res, query(2 * i, l, mid, x));
    else return min(res, query(2 * i + 1, mid + 1, r, x));
}

void add_line(int slope, int y_intercept) {
    add_line(1, 0, MXN - 1, Line(slope, y_intercept));
}

int query(int x) {
    return query(1, 0, MXN - 1, x);
}

void solve() {
    cin >> N;

    vector<int> H(N + 1, 0), W(N + 1, 0); 
    for (int i = 1; i <= N; i++)
        cin >> H[i];

    for (int i = 1; i <= N; i++)
        cin >> W[i];

    vector<int> dp(N + 1, INF);
    dp[1] = 0;

    int sum = W[1];

    add_line(-2 * H[1], H[1] * H[1] + dp[1] - sum);

    for (int i = 2; i <= N; i++) {
        dp[i] = query(H[i]) + H[i] * H[i] + sum;

        sum += W[i];

        add_line(-2 * H[i], H[i] * H[i] + dp[i] - sum);
    }

    cout << dp[N];
}

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

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62956 KB Output is correct
2 Correct 33 ms 62956 KB Output is correct
3 Correct 33 ms 62956 KB Output is correct
4 Correct 34 ms 63212 KB Output is correct
5 Correct 33 ms 62956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 65260 KB Output is correct
2 Correct 79 ms 66284 KB Output is correct
3 Correct 78 ms 66284 KB Output is correct
4 Correct 84 ms 66284 KB Output is correct
5 Correct 68 ms 66284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62956 KB Output is correct
2 Correct 33 ms 62956 KB Output is correct
3 Correct 33 ms 62956 KB Output is correct
4 Correct 34 ms 63212 KB Output is correct
5 Correct 33 ms 62956 KB Output is correct
6 Correct 81 ms 65260 KB Output is correct
7 Correct 79 ms 66284 KB Output is correct
8 Correct 78 ms 66284 KB Output is correct
9 Correct 84 ms 66284 KB Output is correct
10 Correct 68 ms 66284 KB Output is correct
11 Correct 83 ms 66540 KB Output is correct
12 Correct 82 ms 66284 KB Output is correct
13 Correct 73 ms 66412 KB Output is correct
14 Correct 81 ms 66540 KB Output is correct
15 Correct 66 ms 66156 KB Output is correct
16 Correct 65 ms 66284 KB Output is correct
17 Correct 60 ms 66412 KB Output is correct
18 Correct 61 ms 66412 KB Output is correct