oj.uz

Submission #714031

# Submission time Handle Problem Language Result Execution time Memory
714031 2023-03-23T15:33:08 Z stevancv Building Bridges (CEOI17_building) C++14
100 / 100
 80 ms 65620 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e6 + 2;
const ll linf = 1e18;
ll h[N], w[N];
struct Line {
    ll a, b;
    Line() {
        a = b = linf;
    }
    Line(ll aa, ll bb) {
        a = aa; b = bb;
    }
    ll F(int x) {
        if (a == linf && b == linf) return linf;
        return a * x + b;
    }
} st[4 * M];
void Add(int node, int l, int r, Line lin) {
    int mid = l + r >> 1;
    bool le = lin.F(l) < st[node].F(l);
    bool mi = lin.F(mid) < st[node].F(mid);
    if (mi) swap(lin, st[node]);
    if (l == r) return;
    if (le != mi) Add(2 * node, l, mid, lin);
    else Add(2 * node + 1, mid + 1, r, lin);
}
ll Get(int node, int l, int r, int x) {
    ll ans = st[node].F(x);
    if (l == r) return ans;
    int mid = l + r >> 1;
    if (x <= mid) smin(ans, Get(2 * node, l, mid, x));
    else smin(ans, Get(2 * node + 1, mid + 1, r, x));
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    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];
    for (int i = 1; i <= 4 * n; i++) st[i] = Line();
    Add(1, 0, M, Line(-2 * h[1], h[1] * h[1] - w[1]));
    ll sol = linf;
    for (int i = 2; i < n; i++) {
        ll o = Get(1, 0, M, h[i]) + h[i] * h[i] + w[i - 1];
        Add(1, 0, M, Line(-2 * h[i], o + h[i] * h[i] - w[i]));
    }
    cout << Get(1, 0, M, h[n]) + h[n] * h[n] + w[n - 1] << en;
    return 0;
}

Compilation message

building.cpp: In function 'void Add(int, int, int, Line)':
building.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'long long int Get(int, int, int, int)':
building.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'int main()':
building.cpp:52:8: warning: unused variable 'sol' [-Wunused-variable]
   52 |     ll sol = linf;
      |        ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 26 ms 62912 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 26 ms 62932 KB Output is correct
5 Correct 29 ms 62860 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 65516 KB Output is correct
2 Correct 67 ms 65468 KB Output is correct
3 Correct 69 ms 65580 KB Output is correct
4 Correct 61 ms 65372 KB Output is correct
5 Correct 65 ms 65376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 26 ms 62912 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 26 ms 62932 KB Output is correct
5 Correct 29 ms 62860 KB Output is correct
6 Correct 69 ms 65516 KB Output is correct
7 Correct 67 ms 65468 KB Output is correct
8 Correct 69 ms 65580 KB Output is correct
9 Correct 61 ms 65372 KB Output is correct
10 Correct 65 ms 65376 KB Output is correct
11 Correct 72 ms 65620 KB Output is correct
12 Correct 73 ms 65484 KB Output is correct
13 Correct 66 ms 65576 KB Output is correct
14 Correct 80 ms 65560 KB Output is correct
15 Correct 64 ms 65364 KB Output is correct
16 Correct 60 ms 65424 KB Output is correct
17 Correct 56 ms 65484 KB Output is correct
18 Correct 58 ms 65468 KB Output is correct