oj.uz

Submission #868299

# Submission time Handle Problem Language Result Execution time Memory
868299 2023-10-31T03:17:07 Z phudzctg Building Bridges (CEOI17_building) C++14
100 / 100
 67 ms 13140 KB 
#include <bits/stdc++.h>
#define N 100001
#define maxx 100000
#define inf 1000000000

using namespace std;
typedef long long ll;
typedef pair<ll, ll> line;
int n, M, h[N], w[N], a[N];
ll dp[N];
ll f(line l, int x) {
    if (l.first == inf && l.second == inf)
        return ll(inf) * inf;
    return l.first * a[x] + l.second;
}
line L[4 * N];
void add_line(line nw, int v = 1, int l = 1, int r = M) {
    if (f(nw, l) >= f(L[v], l) && f(nw, r) >= f(L[v], r))
        return;
    if (f(nw, l) <= f(L[v], l) && f(nw, r) <= f(L[v], r)) {
        swap(L[v], nw);
        return;
    }
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(L[v], l);
    bool mid = f(nw, m) < f(L[v], m);
    if(mid)
        swap(L[v], nw);
    if(r - l == 1)
        return;
    else
        if(lef != mid) {
            add_line(nw, 2 * v, l, m);
        } else {
            add_line(nw, 2 * v + 1, m, r);
        }
}

ll get(int x, int v = 1, int l = 1, int r = M) {
    int m = (l + r) / 2;
    if(r - l == 1)
        return f(L[v], x);
    else
        if(x < m)
            return min(f(L[v], x), get(x, 2 * v, l, m));

        else
            return min(f(L[v], x), get(x, 2 * v + 1, m, r));
}
#define task "BUILD"
int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> h[i];
    for(int i = 1; i <= n; ++i)
        cin >> w[i];

    set<int> tmp;
    for(int i = 1; i <= n; ++i)
        tmp.insert(h[i]);
    M = 0;
    for(int x : tmp)
        a[++M] = x;
    for(int i = 1; i <= n; ++i)
        h[i] = lower_bound(a + 1, a + M + 1, h[i]) - a;

    for(int i = 1; i <= 4 * M; ++i)
        L[i] = make_pair(inf, inf);
    dp[1] = -w[1];
    add_line(make_pair(-2 * a[h[1]], dp[1] + ll(a[h[1]])*a[h[1]]));
    for(int i = 2; i <= n; ++i) {
        dp[i] = ll(a[h[i]]) * a[h[i]] - w[i] + get(h[i]);
        add_line(make_pair(-2 * a[h[i]], dp[i] + ll(a[h[i]])*a[h[i]]));
    }

    ll ans = dp[n];
    for(int i = 1; i <= n; ++i)
        ans += w[i];

    cout << ans;

}

Compilation message

building.cpp: In function 'int main()':
building.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6500 KB Output is correct
2 Correct 47 ms 6484 KB Output is correct
3 Correct 46 ms 6436 KB Output is correct
4 Correct 40 ms 4052 KB Output is correct
5 Correct 51 ms 13140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 47 ms 6500 KB Output is correct
7 Correct 47 ms 6484 KB Output is correct
8 Correct 46 ms 6436 KB Output is correct
9 Correct 40 ms 4052 KB Output is correct
10 Correct 51 ms 13140 KB Output is correct
11 Correct 63 ms 11348 KB Output is correct
12 Correct 66 ms 11500 KB Output is correct
13 Correct 33 ms 4100 KB Output is correct
14 Correct 67 ms 11344 KB Output is correct
15 Correct 53 ms 13136 KB Output is correct
16 Correct 56 ms 13140 KB Output is correct
17 Correct 13 ms 3932 KB Output is correct
18 Correct 13 ms 3932 KB Output is correct