oj.uz

Submission #887264

# Submission time Handle Problem Language Result Execution time Memory
887264 2023-12-14T07:01:09 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 43 ms 37172 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define MASK(x) (1 << x)

const int maxN = 1e5 + 7;
const int maxVal = (int)1e6 + 7;
const int maxLog = 63 - __builtin_clzll(maxVal) + 2;
const int INF = (int)1e18 + 7;

int n, h[maxN], w[maxN];

long long psW[maxN], f1[1007], f[maxN];

struct Line {
    long long a, b;
    Line() {
        a = 0;
        b = INF;
    }
    Line(long long _a, long long _b) {
        a = _a;
        b = _b;
    }
    long long operator() (long long x) {
        return a * x + b;
    }
} node[MASK(maxLog)];

void ins(int id, int l, int r, Line L) {
    if(l > r) return;
    if(l == r) {
        node[id] = L;
        return;
    }
    int m = (l + r) >> 1;
    if(node[id].a > L.a) swap(node[id], L);
    if(node[id](m) > L(m)) {
        swap(node[id], L);
        ins(id << 1 | 1, m + 1, r, L);
    }else ins(id << 1, l, m, L);
}

void ins(Line L) {
    ins(1, 0, maxVal, L);
}

long long get(int id, int l, int r, int x) {
    if(l > r) return INF;
    if(l == r) return node[id](x);
    int m = (l + r) >> 1;
    if(x <= m) return min(node[id](x), get(id << 1, l, m, x));
    return min(node[id](x), get(id << 1 | 1, m + 1, r, x));
}

long long get(int x) {
    return get(1, 0, maxVal, x);
}

long long sqr(long long x) {
    return x * x;
}

void subtask1() {
    psW[0] = 0;
    for (int i = 1; i <= n; i++) {
        psW[i] = psW[i - 1] + w[i];
    }
    memset(f1, 0x3f, sizeof f1);
    f1[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            f1[i] = min(f1[i], f1[j] + sqr(h[i] - h[j]) + psW[i - 1] - psW[j]);
        }
    }
    cout << f1[n] << '\n';
}

void subtask2() {
    f[1] = 0;
    for (int i = 1; i <= n; i++) {
        psW[i] = psW[i - 1] + w[i];
    }
    ins(Line(-2 * h[1], sqr(h[1]) - psW[1])); // ax + b
    for(int i = 2; i <= n; i++) {
        f[i] = get(h[i]) + sqr(h[i]) + psW[i - 1];
        ins(Line(-2 * h[i], f[i] - psW[i] + sqr(h[i])));
    }
    cout << f[n] << '\n';
}

signed main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    if (n <= 1000) subtask1();
        else subtask2();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35420 KB Output is correct
4 Correct 6 ms 35416 KB Output is correct
5 Correct 8 ms 35420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36184 KB Output is correct
2 Correct 38 ms 36184 KB Output is correct
3 Correct 37 ms 36184 KB Output is correct
4 Correct 35 ms 36188 KB Output is correct
5 Correct 31 ms 36188 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35420 KB Output is correct
4 Correct 6 ms 35416 KB Output is correct
5 Correct 8 ms 35420 KB Output is correct
6 Correct 37 ms 36184 KB Output is correct
7 Correct 38 ms 36184 KB Output is correct
8 Correct 37 ms 36184 KB Output is correct
9 Correct 35 ms 36188 KB Output is correct
10 Correct 31 ms 36188 KB Output is correct
11 Correct 43 ms 36956 KB Output is correct
12 Correct 43 ms 37072 KB Output is correct
13 Correct 36 ms 36956 KB Output is correct
14 Correct 42 ms 37172 KB Output is correct
15 Correct 31 ms 37052 KB Output is correct
16 Correct 31 ms 37172 KB Output is correct
17 Correct 25 ms 37172 KB Output is correct
18 Correct 24 ms 36952 KB Output is correct